dinic+spfa 63pts,求救
查看原帖
dinic+spfa 63pts,求救
261574
rmzls楼主2023/8/22 12:07

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
int head[N],nxt[N],ret,val[N],to[N],ans,cur[N],d[N],u,v,w,c,n,m,S,T,cnt=1,vis[N],cost[N];
void add(int u,int v,int w,int c){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	val[cnt]=w;
	cost[cnt]=c;
	head[u]=cnt;
	to[++cnt]=u;
	nxt[cnt]=head[v];
	val[cnt]=0;
	cost[cnt]=-c;
	head[v]=cnt;
}
int spfa(){
	for(int i=1;i<=n;i++){
		d[i]=INT_MAX;
	}
	queue<int>q;
	q.push(S);d[S]=0;vis[S]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		cur[x]=head[x];vis[x]=0;
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i];
			if(!val[i]||d[y]<=d[x]+cost[i]){
				continue;
			}
			d[y]=d[x]+cost[i];
			cur[y]=head[y];
			if(!vis[y]){
				q.push(y);vis[y]=1;
			}
		}
	}
	return d[T]==INT_MAX?0:1;
}
int dfs(int x,int sum){
	if(x==T||sum==0){
		return sum;
	}
	int res=0,fl;vis[x]=1;
	for(int i=cur[x];i;i=nxt[i]){
		if(sum==0){
			return res;
		}
		cur[x]=i;
		int y=to[i];
		if(!val[i]||vis[y]||d[y]!=d[x]+cost[i]){
			continue;
		}
		fl=dfs(y,min(sum,val[i]));
		if(!fl){
			d[y]=INT_MAX;
			continue;
		}
		val[i]-=fl;val[i^1]+=fl;
		res+=fl;sum-=fl;ret+=fl*cost[i];
	}
	vis[x]=0;
	return res;
}
void dicic(){
	while(spfa()){
		int x;
		while((x=dfs(S,INT_MAX))){
			ans+=x;
		}
	}
}
signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&S,&T);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld%lld",&u,&v,&w,&c);
		add(u,v,w,c);
	}
	dicic();
	printf("%lld %lld\n",ans,ret);
	return 0;
}
2023/8/22 12:07
加载中...