dinic Wa 63pts 求调
查看原帖
dinic Wa 63pts 求调
386892
REMAC楼主2023/1/15 13:41
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int inf=0x3f3f3f3f3f3f3f3f;

const int maxn=5010;

using Pii=pair<int,int>;

int dis[maxn],cur[maxn],vis[maxn],inq[maxn];

struct Dinic{
	
	int s,t;
	
	int cost=0;
	
	struct Edge{
		int v,r,cp,w;
	};
	
	vector<Edge> g[maxn];
	
	void addEdge(int u,int v,int c,int w)
	{
		g[u].push_back(Edge{v,c,g[v].size(),w});
		g[v].push_back(Edge{u,0,g[u].size()-1,w});
	}
	
	bool spfa()
	{
		memset(dis,0x3f,sizeof dis);
		memset(inq,0,sizeof inq);
		dis[s]=0;
		queue<int> que;
		que.push(s),inq[s]=1;
		while(!que.empty())
		{
			int u=que.front();
			que.pop(); inq[u]=0;
			for(auto e:g[u]) if(e.r){
				if(dis[e.v]>dis[u]+e.w){
					dis[e.v]=dis[u]+e.w;
					if(!vis[e.v]) que.push(e.v),inq[e.v]=1;
				}
			}
		}
		return dis[t]!=inf;
	}
	int dfs(int u,int f)
	{
		if(u==t||f==0) return f;
		vis[u]=1;
		int ret=0;
		for(int &i=cur[u];i<g[u].size();i++)
		{
			auto &e=g[u][i];
			int v=e.v, &r=e.r, &cp=g[v][e.cp].r, w=e.w;
			if(!vis[v]&&dis[v]==dis[u]+w)
			{
				int flow=dfs(v,min(f-ret,r));
				r-=flow,cp+=flow,ret+=flow,cost+=flow*w;
			}
			if(f==ret) break;
		}
		vis[u]=0;
		return ret;
	}
	
	int maxFlow()
	{
		cost=0;
		int ret=0;
		while(spfa()) 
		{
			memset(cur,0,sizeof cur);
			memset(vis,0,sizeof vis);
			ret+=dfs(s,inf);
		}
		return ret;
	}
} dinic;

main(){
	int n,m;
	cin>>n>>m>>dinic.s>>dinic.t;
	for(int i=1;i<=m;i++)
	{
		int u,v,c,w;
		cin>>u>>v>>c>>w;
		dinic.addEdge(u,v,c,w);
	}
	cout<<dinic.maxFlow()<<' ';
	cout<<dinic.cost;
}
2023/1/15 13:41
加载中...