啊啊啊啊啊我不知道哪里出了奇怪的问题
查看原帖
啊啊啊啊啊我不知道哪里出了奇怪的问题
188879
VioletIsMyLove楼主2023/10/6 20:53

费用流在一次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;
}
2023/10/6 20:53
加载中...