求助大佬,蒻鸡刚学网络流,请dalao指点
查看原帖
求助大佬,蒻鸡刚学网络流,请dalao指点
239251
Robert123456楼主2021/8/24 19:19

Wa了两个点,Re了三个点!!! 以下代码:

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+1000;
const int M=5e4+100;
const int INF=0x7f7f7f7f;

int a,b,c,d;
int end;

int src,des,ans,dis[N];
int m=1,adj[N],nxt[N],go[M],cap[M],cost[M];
bool vis[N],walk[N];
queue<int> que;

inline void addEdge(int u,int v,int f,int w){
	nxt[++m]=adj[u],adj[u]=m,go[m]=v,cap[m]=f,cost[m]=w;
	nxt[++m]=adj[v],adj[v]=m,go[m]=u,cap[m]=0,cost[m]=-w;
}

inline bool spaf(){
	memset(dis,INF,sizeof(dis));
	memset(walk,0,sizeof(walk));
	que.push(src),dis[src]=0;
	int u,v,e;
	while(!que.empty()){
		u=que.front(),que.pop();
		vis[u]=false;
		for(e=adj[u];e;e=nxt[e]){
			if(cap[e]>0&&dis[u]+cost[e]<dis[v=go[e]]){
				dis[v]=dis[u]+cost[e];
				if(!vis[v]){
					vis[v]=1;
					que.push(v);
				}
			}
		}
	}
	return dis[des]<INF;
}

int dfs(int u,int flow){
	if(u==des){
		ans+=flow*dis[des];
		return flow;
	}
	walk[u]=1;
	int v,e,res=0,delta;
	for(e=adj[u];e;e=nxt[e]){
		if(!walk[v=go[e]]&&cap[e]>0&&dis[u]+cost[e]==dis[v]){
			delta=dfs(v,min(cap[e],flow-res));
			if(delta){
				cap[e]-=delta;
				cap[e^1]-=delta;
				res+=delta;
				if(res==flow) break;
			}
		}
	}
	return res;
}

int slove(){
	ans=0;
	while(spaf()){
		end+=dfs(src,INF);
	}
	return ans;
}


int main(){
	cin>>a>>b>>c>>d;
	for(int i=1;i<=b;i++){
		int u,v,f,w;
		cin>>u>>v>>f>>w;
		addEdge(u,v,f,w);
	}
	src=c;
	des=d;
	cout<<end<<' '<<slove()<<endl;




	return 0;
}

2021/8/24 19:19
加载中...