本蒟蒻费用流EK+spfa,73pts求调
查看原帖
本蒟蒻费用流EK+spfa,73pts求调
177832
Ink_Sunk楼主2022/8/8 16:48
#include <cstdio>
#include <algorithm>
#include <cstring>

#define maxn 5005
#define maxm 150050
#define INF 0x3f3f3f3f
#define int long long

using namespace std;

inline int read(){
	int x=0; char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
	return x;
}

int n,m,s,t,fa[maxn],flow[maxn],fare[maxn];

int Head[maxm],Next[maxm],to[maxm],w[maxm],Cost[maxn],cnt=0;

bool vis[maxn];

inline void add(int u,int v,int c,int cst){
	Next[cnt]=Head[u]; to[cnt]=v; w[cnt]=c; Cost[cnt]=cst; Head[u]=cnt++;
}

inline bool spfa(){
	memset(fare,0x3f,sizeof(fare));
	memset(flow,0,sizeof(flow));
	int q[maxn],top=0,tail=-1;
	q[++tail]=s;  vis[s]=true; flow[s]=INF; fare[s]=0;
	while(top<=tail){
		int now=q[top]; top++;
		vis[now]=false;
		for(int i=Head[now];i!=-1;i=Next[i]){
			if(w[i]<=0) continue;
			if(fare[to[i]]<=fare[now]+Cost[i]) continue;
			fare[to[i]]=fare[now]+Cost[i];
			flow[to[i]]=min(flow[now],w[i]);
			fa[to[i]]=i;
			if(!vis[to[i]]){
				if(tail+1>=maxn) top=0,tail=-1;
				q[++tail]=to[i];
				vis[to[i]]=true;
			}
		}
	}
	return flow[t]>0;
}

inline void EK(){
	int res=0,cost=0;
	while(spfa()){
		res+=flow[t]; cost+=flow[t]*fare[t];
		for(int i=t;i!=s;i=to[fa[i]^1]) w[fa[i]]-=flow[t],w[fa[i]^1]+=flow[t];
	}
	printf("%lld %lld",res,cost);
}

signed main(){
	memset(Head,-1,sizeof(Head));
	n=read(); m=read(); s=read(); t=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),c=read(),w=read();
		add(u,v,c,w); add(v,u,0,-w);
	}
	EK();
	return 0;
}
2022/8/8 16:48
加载中...