最小费用最大流板子的SPFA打出死循环了,求调
查看原帖
最小费用最大流板子的SPFA打出死循环了,求调
734049
__Cby___楼主2024/1/4 21:28
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
long long int n,m,s,e;
struct node{
	int uu,ww;
};
vector<node> g[5025];
int cf[5025][5025];
int mi[5025];
int pre[5025];
bool vis[5025];
long long int dis[5025];
bool bfs(){
	for(int i=1;i<=n;i++)dis[i]=2123456789876;
	for(int i=1;i<=n;i++)vis[i]=0;
	queue<int> q;
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	mi[s]=2123456789;
	bool y=0;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		vis[t]=0;
		for(auto vt:g[t]){
			int v=g[t][vt].uu;
			int w=g[t][vt].ww;
			if(cf[t][v]>0&&dis[v]>dis[t]+w){
				pre[v]=t;
				mi[v]=min(mi[t],cf[t][v]);
				dis[v]=dis[t]+w;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				} 
				if(v==e)y=1;
			}
		} 
	}
	return y;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s>>e;
	for(int i=1;i<=m;i++){
		int u,v,w,q;
		cin>>u>>v>>w>>q;
		g[u].push_back({v,q});
		g[v].push_back({u,-q});
		cf[u][v]+=w;
	}
	long long int ans=0;
	long long int ans2=0;
	while(bfs()){
		int t=e;
		while(t!=s){
			int u=pre[t];
			cf[t][u]+=mi[e];
			cf[u][t]-=mi[e];
			t=u;
		}
		ans+=mi[e];
		ans2+=(long long)mi[e]*dis[e];
	}
	cout<<ans<<" "<<ans2<<endl;
	return 0; 
}
2024/1/4 21:28
加载中...