第一道网络流题，纪念下~~~
题目链接：
?id=1459
题目大意：
一个电力网络包含很多节点(发电站、消费者以及中转站)和电力传输线。所有发电站不消耗电力，
所有消费者不产生电力，所有中转站不产生也不消耗电力。在网络中，任意两点u和v之间最多只
有一条传输线的存在，且能够从u望v传输最多w单位容量。计算整个网络的最大电力消耗。
思路：
一道非常基础、非常典型的网络流题目。每个发电站当做一个源点，每个消费者当做一个汇点。但
是这样子并不适合任何一种求网络最大流算法。那么现在设置一个超级源点，连向所有发电站，，容
量为发电站的点容量。再来设置一个超级汇点，让所有的消费者连向超级汇点，边容量为消费者的
点容量。下面就可以通过最大流算法来解决问题了。这里用Edmond-Karp算法来做。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int MAXN = 220;int Map[MAXN][MAXN],pre[MAXN];int N,NP,NC,M;bool EkBFS(int start,int end){queue<int> Q;bool vis[MAXN];memset(vis,false,sizeof(vis));memset(pre,-1,sizeof(pre));Q.push(start);vis[start] = true;while( !Q.empty() ){int u = Q.front();if(u == end)return true;Q.pop();for(int i = 0; i <= N+1; ++i){if(Map[u][i] && !vis[i]){vis[i] = true;pre[i] = u;Q.push(i);}}}return false;}int EkMaxFlow(int start,int end){int v,Ans = 0,MinN;while(EkBFS(start,end)){MinN = 0xffffff0;v = end;while( pre[v] != -1){MinN = min(MinN,Map[pre[v]][v]);v = pre[v];}Ans += MinN;v = end;while( pre[v] != -1){Map[pre[v]][v] -= MinN;Map[v][pre[v]] += MinN;v = pre[v];}}return Ans;}int main(){char ch;int u,v,w;while(~scanf("%d %d %d %d ",&N,&NP,&NC,&M)){memset(Map,0,sizeof(Map));for(int i = 0; i < M; ++i){while( (ch = getchar())!='(' );scanf("%d",&u);getchar();scanf("%d",&v);getchar();scanf("%d",&w);Map[u][v] = w;}for(int i = 0; i < NP+NC; ++i){while( (ch = getchar())!='(' );scanf("%d",&u);getchar();scanf("%d",&w);if(i < NP)Map[N][u] = w;elseMap[u][N+1] = w;}printf("%d\n",EkMaxFlow(N,N+1));}return 0;}
像一颗深绿色的宝石镶嵌在云南大地上，
