POJ1459--Power Network(多源点多汇点)

最大流模版题。多源点多汇点，只需再添加两个点，将其中一个点与各个源点连接，并将其最为源点，汇点同理。

#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;

const int maxn=205*205;
const int INF=999999999;

struct Edge
{
	int from,to,cap,flow;
};

int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn];

void init()
{
	for(int i=0;i<maxn;i++)
		G[i].clear();
	memset(vis,0,sizeof(vis));
	memset(d,0,sizeof(d));
	memset(cur,0,sizeof(cur));
}

bool BFS()
{
	memset(vis,0,sizeof(vis));
	queue<int> Q;
	Q.push(s);
	d[s]=0;
	vis[s]=1;
	while(!Q.empty())
	{
		int x=Q.front();
		Q.pop();
		for(int i=0;i<G[x].size();i++)
		{
			Edge e=edges[G[x][i]];
			if(!vis[e.to] && e.cap>e.flow)
			{
				vis[e.to]=1;
				d[e.to]=d[x]+1;
				Q.push(e.to);
			}
		}
	}
	return vis[t];
}

int DFS(int x,int a)
{
	if(x==t || a==0)
		return a;
	int flow=0,f;
	for(int i=cur[x];i<G[x].size();i++)
	{
		Edge& e=edges[G[x][i]];
		if(d[x]+1 == d[e.to] && (f = DFS(e.to,min(a,e.cap-e.flow)))>0)
		{
			e.flow+=f;
			edges[G[x][i]^1].flow-=f;
			flow+=f;
			a-=f;
			if(a==0)
				break;
		}
	}
	return flow;
}

int Maxflow(int s,int t)
{
	int flow=0;
	while(BFS())
	{
		memset(cur,0,sizeof(cur));
		flow+=DFS(s,INF);
	}
	return flow;
}

void AddEdge(int from,int to,int cap)
{
	struct Edge e;
	e.from=from,e.to=to,e.cap=cap,e.flow=0;
	edges.push_back(e);
	e.from=to,e.to=from,e.cap=0,e.flow=0;
	edges.push_back(e);
	m=edges.size();
	G[from].push_back(m-2);
	G[to].push_back(m-1);
}

int main()
{
	int np,nc,k;
	while(scanf("%d%d%d%d",&n,&np,&nc,&k)!=EOF)
	{
		int u,v,l;
		char ch;
		init();
		for(int i=0;i<k;i++)
		{
			cin>>ch>>u>>ch>>v>>ch>>l;
			AddEdge(u+1,v+1,l);
		}
		for(int i=0;i<np;i++)
		{
			cin>>ch>>v>>ch>>l;
			AddEdge(0,v+1,l);
		}
		for(int i=0;i<nc;i++)
		{
			cin>>ch>>u>>ch>>l;
			AddEdge(u+1,n+1,l);
		}
		s=0,t=n+1;
		int ans=Maxflow(s,t);
		printf("%d\n",ans);
	}
	return 0;
}