萌新袜子初学OI求助
查看原帖
萌新袜子初学OI求助
186045
itisover楼主2021/3/29 11:45

为什么spfa会死循环呢?(⊙o⊙)?

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1e5+5,INF=1e9;
int src,dst;
int maxflow,mincost,last[M],flow[M],pre[M],dis[M];
bool vis[M];
struct Edge{
	int to,next,flow,dis;
}edge[M<<1];
int hd[M<<1],tote;
queue<int> q;
void adde(int from,int to,int flow,int dis){
	edge[++tote].next=hd[from];
	edge[tote].to=to;
	edge[tote].flow=flow;
	edge[tote].dis=dis;
	hd[from]=tote;
}
bool spfa(int s,int t){
	memset(dis,0x3f,sizeof(dis));memset(flow,0x3f,sizeof(flow));memset(vis,0,sizeof(vis));
	q.push(s);vis[s]=1;dis[s]=0;pre[t]=-1;
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=0;
		for(int i=hd[u];i;i=edge[i].next){
			int v=edge[i].to;
			if(edge[i].flow>0&&dis[u]+edge[i].dis<dis[v]){
				dis[v]=dis[u]+edge[i].dis;
				pre[v]=u;
				last[v]=i;
				flow[v]=min(flow[u],edge[i].flow);
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return pre[t]!=-1;
}
void MCMF(){
	while(spfa(src,dst)){
		int now=dst;
		//maxflow+=flow[dst];
		mincost+=flow[dst]*dis[dst];
		while(now!=src){
			edge[last[now]].flow-=flow[dst];
			edge[last[now]^1].flow+=flow[dst];
			now=pre[now];
		}
	}
}
int m,n;
int main(){
	cin>>m>>n;
	src=0,dst=n*m+1;
	for(int i=1,x;i<=m;i++) cin>>x,adde(src,i,x,0),adde(i,src,0,0);
	for(int j=1,x;j<=n;j++) cin>>x,adde(j+m,dst,x,0),adde(dst,j+m,0,0);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			int x;
			cin>>x;
			adde(i,j+m,INF,x);
			adde(j+m,i,0,-x);
		}
	}
	MCMF();
	printf("%d\n",mincost);
	return 0;
}
2021/3/29 11:45
加载中...