Power Network POJ - 1459 [网络流模板]

http://poj.org/problem?id=1459

嗯,网络流模板...多源点多汇点的图,超级汇点连发电厂,用户连接超级汇点

Status	Accepted
Time	391ms
Memory	1588kB
Length	2166
Lang	G++
Submitted	2018-05-23 14:43:22
Shared
RemoteRunId	18625420

#include <iostream>

#include <string.h>

#include <cmath>

#define ll long long

#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define pp pair<int,int>

#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)

#define	per(ii,a,b) for(int ii=a;ii>=b;ii--)

#define show(x) cout<<#x<<"="<<x<<endl

#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl

#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl

#define showa(a,b) cout<<#a<<'['<<b<<"]="<<b[a]<<endl

using namespace std;

const int maxn=1e5+10;

const int maxm=1e6+10;

const ll INF=0x3f3f3f3f3f;

int casn,n,np,nc,m,k;

struct node {int to;ll cap;int next;}e[maxm];

int ss,tt,head[maxn],nume,dis[maxn],q[maxn];

inline void addx(int a,int b,ll c){

	e[++nume]=(node){b,c,head[a]};

	head[a]=nume;

}

inline void add(int a,int b,ll c){

	addx(a,b,c);addx(b,a,0);

}

bool bfs(int s=ss,int t=tt){

	int top=0,end=1;

	q[0]=s;

	for(int i=0;i<=t;i++) dis[i]=0;

	dis[s]=1;

	while(top!=end){

		int now=q[top++];top%=maxn;

		for(int i=head[now];i;i=e[i].next){

			int to=e[i].to;

			if(!dis[to]&&e[i].cap){

				dis[to]=dis[now]+1;

				if(to==t)break;

				q[end++]=to;end%=maxn;

			}

		}

	}

	return dis[t];

}

ll dfs(int now=ss,ll last=INF){

	if(now==tt)return last;

	ll flow=0,det;

	for(int i=head[now];i;i=e[i].next){

		int to=e[i].to;

		if(e[i].cap&&dis[to]==dis[now]+1){

			det=dfs(to,min(last-flow,e[i].cap));

			flow+=det;

			e[i].cap-=det;

			e[i^1].cap+=det;

			if(flow==last) return last;

		}

	}

	if(flow==0) dis[now]=-1;

	return flow;

}

int main(){

//#define test

#ifdef test

	freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);

#endif

	int nc,np;

	IO;

	while(cin>>n>>np>>nc>>m){

		char ch;

		memset(head,0,sizeof head);

		nume=1;

		ss=n+9,tt=n+10;

		rep(i,1,m) {

			int a,b,c;

			cin>>ch>>a>>ch>>b>>ch>>c;

			if(a==b) continue;

			add(a,b,c);

		}

		rep(i,1,np){

      int a,b,c;

      cin>>ch>>a>>ch>>c;

      add(ss,a,c);

		}

		rep(i,1,nc){

			int a,b,c;

			cin>>ch>>a>>ch>>c;

			add(a,tt,c);

		}

		int ans=0;

		while(bfs()){

//      show(1);

			ans+=dfs();

//			show(ans);

		}

		cout<<ans<<'\n';

	}

#ifdef test

	fclose(stdin);fclose(stdout);system("out.txt");

#endif

	return 0;

}