题意：有n个节点，np个发电站，nc个消耗站，其余的为中转站，有m条路径，求最大的电流量。
求解：增加一个源点和一个汇点，转化为最大网络流问题，使用Edmonds_Karp算法
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int n,np,nc,m;
#define maxn 105
#define INF 0xFFFFFFF
int cap[maxn][maxn],flow[maxn][maxn];
int pre[maxn],res[maxn];//res[i] 残量
int Edmonds_Karp(int start,int end)
{int maxflow=0;memset(flow,0,sizeof(flow));memset(pre,0,sizeof(pre));queue<int> q;while(true){memset(res,0,sizeof(res));res[start]=INF;q.push(start);while(!q.empty()) //BFS寻找增广路{int u=q.front();q.pop();for(int v=1;v<=end;v++)if(!res[v]&&cap[u][v]>flow[u][v]){res[v]=min(res[u],cap[u][v]-flow[u][v]);//start-v路径上的最小残量//记录v的父亲，并加入队列中pre[v]=u;q.push(v);}}if(res[end]==0) return maxflow;//无法继续更新最大流量，则当前流已经是最大流for(int u=end;u!=start;u=pre[u])//从汇点往回走{flow[pre[u]][u]+=res[end];//更新正向流flow[u][pre[u]]-=res[end];//更新反向流}maxflow+=res[end]; //更新从s流出的总流量}return maxflow;
}
int main()
{char tmp;int a,b,c,d;while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF){memset(cap,0,sizeof(cap));for(int i=1;i<=m;i++){scanf("%c",&tmp);while(tmp!='('){scanf("%c",&tmp);}scanf("%d",&a); a=a+2;scanf("%c",&tmp);scanf("%d",&b); b=b+2;scanf("%c",&tmp);scanf("%d",&d);cap[a][b]=d;}for(int i=1;i<=np;i++){scanf("%c",&tmp);while(tmp!='('){scanf("%c",&tmp);}scanf("%d",&a); a=a+2;scanf("%c",&tmp);scanf("%d",&d);cap[1][a]=d;}for(int i=1;i<=nc;i++){scanf("%c",&tmp);while(tmp!='('){scanf("%c",&tmp);}scanf("%d",&a);a=a+2;scanf("%c",&tmp);scanf("%d",&d);cap[a][n+2]=d;}n=n+2;int ans=Edmonds_Karp(1,n);printf("%d\n",ans);}return 0;
}