费用流在一次SPFA之后就结束了,并没有跑满最大流,题解的代码都是可以接着沿着反向边跑满最大流,但是我的代码就是不行。。。已经对比双方代码半个小时了,还是没找到哪里有问题啊啊啊
#include<bits/stdc++.h>
using namespace std;
int n,m,S,T,mc,mf;
int q[405],Dis[405];
int flw[405],lst[405],pre[405];
int lnk[205],nxt[405],son[405],v[405],dis[405],tot=1;
bool vis[405];
string ct;
map<string,int>c;
inline int read(){
int ret=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
return ret*f;
}
void add(int x,int y,int z,int g){son[++tot]=y;nxt[tot]=lnk[x];v[tot]=z;dis[tot]=g;lnk[x]=tot;}
int SPFA(){
memset(Dis,128,sizeof Dis);
memset(flw,127,sizeof flw);
int hed=0,til=0;q[++til]=S;
Dis[S]=pre[T]=0;
while(hed^til){
vis[q[++hed]]=0;
for(int i=lnk[q[hed]];i;i=nxt[i])
if(v[i]&&Dis[son[i]]<Dis[q[hed]]+dis[i]){
Dis[son[i]]=Dis[q[hed]]+dis[i];
lst[son[i]]=i;pre[son[i]]=q[hed];
flw[son[i]]=min(flw[q[hed]],v[i]);
if(!vis[son[i]]){q[++til]=son[i];vis[son[i]]=1;}
}
}
return pre[T];
}
void MCMF(){
while(SPFA()){
int now=T;
mc+=flw[T]*Dis[T];mf+=flw[T];
while(now!=S){
v[lst[now]]-=flw[T];
v[lst[now]^1]+=flw[T];
now=pre[now];
}
}
}
int main(){
freopen("P2764.in","r",stdin);
freopen("P2764.out","w",stdout);
n=read();m=read();S=1;T=n<<1;
for(int i=1;i<=n;i++){
cin>>ct;
c[ct]=i;
}
add(S,S+n,2,1);add(S+n,S,0,-1);
add(n,T,2,1);add(T,n,0,-1);
for(int i=2;i<n;i++){add(i,i+n,1,1);add(n+i,i,0,-1);}
for(int i=1;i<=m;i++){
int x,y;
cin>>ct;x=c[ct];
cin>>ct;y=c[ct];
if(y<x)swap(x,y);
add(n+x,y,1<<30,0);
add(n+y,x,0,0);
}
MCMF();
if(mf==1){printf("No Solution!\n");return 0;}
printf("%d\n",mf-2);
return 0;
}