样例不过 Dinic+SPFA 求调
查看原帖
样例不过 Dinic+SPFA 求调
697299
hamster000楼主2024/8/4 20:14
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+10,maxm=5e4+10;
struct flow{
	int hd[maxn],cst[maxm*2],to[maxm*2],nxt[maxm*2],limit[maxm*2],cnt=1;
	int in[maxn];
	void add(int u,int v,int w,int c){
		nxt[++cnt]=hd[u],hd[u]=cnt,to[cnt]=v,limit[cnt]=w,cst[cnt]=c;
		nxt[++cnt]=hd[v],hd[v]=cnt,to[cnt]=u,limit[cnt]=0,cst[cnt]=-c;
	}
	int s,t;
	int dis[maxn],cur[maxn];
	pair<int,int> dfs(int id,long long res){
		if(id==t) return make_pair(res,0);
		long long flow=0,cost=0;
		for(int i=cur[id];i&&res;i=nxt[i]){
			cur[id]=i;
			int it=to[i],c=min((long long)limit[i],res);
			if(limit[i]&&dis[id]+cst[i]==dis[it]){
				auto kk=dfs(it,c);
				int k=kk.first;
				flow+=k,res-=k,limit[i]-=k,limit[i^1]+=k;
				cost=kk.second+kk.first*cst[i];
			}
		}
		if(!flow) dis[id]=0x3f3f3f3f;
		return make_pair(flow,cost);
	}
	
	pair<int,int> mincost(int S,int T){
		t=T;
		long long flow=0,cost=0;
		while(true){//SPFA
			queue<int> q;
			memset(dis,0x3f,sizeof dis);
			memset(in,0,sizeof in);
			memcpy(cur,hd,sizeof hd);
			q.push(S),dis[S]=0;
			while(!q.empty()){
				int t=q.front();
				q.pop();
				in[t]=0;
				for(int i=hd[t];i;i=nxt[i]){
					int it=to[i],d=cst[i];
					if(limit[i]&&dis[i]+d<dis[it]){
						dis[it]=dis[i]+d;
						if(!in[it]) in[it]=1,q.push(it);
					}
				}
			}
			if(dis[t]==0x3f3f3f3f) return make_pair(flow,cost);
			auto f=dfs(S,1e18);
			flow+=f.first;
			cost+=dis[t]*f.second;
		}
	}
}g;
int n,m,s,t;
int main(){
	cin >> n >> m >> s >> t;
	for(int i=1;i<=m;i++){
		int u,v,w,c;
		cin >> u >> v >> w >> c;
		g.add(u,v,w,c);
	}
	pair<int, int> ans = g.mincost(s, t);
	cout << ans.first << " " << ans.second << endl;
	return 0;
}

2024/8/4 20:14
加载中...