2991919_ac_5386ms_16212k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
using namespace std;

class Graph
{
private:
	int n;
	struct edge{int to,cap,back;};
	vector<vector<edge> > adj;

public:
	Graph(int n=2):n(n)
	{
		adj.resize(n);
		for(int i = 0; i < n; i++)	adj[i].clear();
	}

	void Insert(int begin,int end,int cap)
	{
		adj[begin].push_back( (edge){end,cap,adj[end].size()});
		adj[end].push_back( (edge){begin,0,adj[begin].size()-1});
	}

	int Dinic(int s,int t)
	{
		int q[n], prev[n], maxflow=0;
	
		while(1)
		{
           	memset(prev,-1,sizeof(prev));
			int head=0, tail=0;
			int i, u, v, z, flow;

			prev[q[tail++] = s] = -2;
			while(head<tail&&prev[t]==-1)
			{
				for(i = 0, u = q[head++]; i < adj[u].size(); i++)
				{
					if(prev[adj[u][i].to]==-1&&adj[u][i].cap>0)
					{
						prev[q[tail++]=adj[u][i].to] = adj[u][i].back;
					}
				}
			}
			if(prev[t]==-1)break;
			flow = 0;
			for(i = 0; i < adj[t].size(); i++)
			{
				if(adj[ z = adj[t][i].to][adj[t][i].back].cap>0&&prev[z]!=-1)
				{
					flow=adj[z][adj[t][i].back].cap;
					for(u=z,v=prev[u];v>=0;u=adj[u][v].to,v=prev[u])
					{
						flow<?=adj[adj[u][v].to][adj[u][v].back].cap;
					}
					if(!flow)continue;
					maxflow += flow;
					adj[z][adj[t][i].back].cap -= flow;
					adj[t][i].cap+=flow;
				    for(u = z, v = prev[u]; v >= 0; u = adj[u][v].to, v=prev[u])
                    {
						adj[adj[u][v].to][adj[u][v].back].cap-=flow;
					    adj[u][v].cap+=flow;
					}
				}
			}
		}
		return maxflow;
	}

};

int main()
{
	int m, n, i, j, k;
	int a, b, c;

	scanf("%d%d",&n,&m);
	Graph graph(n+2);
	for(i = 1; i <= n; i++)
	{
		scanf("%d%d",&a,&b);
		graph.Insert(0,i,a);
		graph.Insert(i,n+1,b);
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		graph.Insert(a,b,c);
		graph.Insert(b,a,c);
	}
	int ans = graph.Dinic(0,n+1);
	printf("%d\n",ans);

}