题目连接：http://poj.org/problem?id=1459
题目实在是不好懂，直接在网上搜了好多题解看题意。。。对于多源多汇点的这种直接虚拟一个总会点就OK了。
题意：
Sample Input
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)207 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7 (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5 (0)5 (1)2 (3)2 (4)1 (5)4
Sample Output
156
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
2 1 1 2依次表示 共两个节点 生产能量的点1个 消费能量的点1个 传递能量的线2条
(0,1)20 (1,0)10 传递能量线 （起点，终点）最大传递的能量 (0)15 产生能量的点 （产生能量的点）产生的最大能量 (1)20 消费能量的点 （消费能量的点）消费的最大能量
代码：
字符串是弱项啊。。。自己写的老出问题，这边总结了下。
View Code #include#include #include #include #include #define maxn 100000using namespace std;long cap[150][150],flow[150][150],pre[150],temp[150];long n,fac,cum,m;long ek(int n){ memset(flow,0,sizeof(flow)); long f = 0,u,v; queue q; for(;;) { memset(temp,0,sizeof(temp)); temp[n] = maxn; q.push(n); long u,v; while(!q.empty()) { u = q.front(); q.pop(); for(v = 0;v <= n+1;v++) if(!temp[v] && cap[u][v] > flow[u][v]) { pre[v] = u; q.push(v); temp[v] = min(temp[u],cap[u][v]- flow[u][v]); } } if(temp[n+1] == 0) break; for(v = n+1;v != n;v = pre[v]) { flow[pre[v]][v] += temp[n+1]; flow[v][pre[v]] -= temp[n+1]; } f+=temp[n+1]; } return f;}int main(){ while(~scanf("%ld %ld %ld %ld",&n,&fac,&cum,&m)) { long u,v,val; char str[100]; memset(cap,0,sizeof(cap)); while(m--) { scanf("%s",str); sscanf(str,"(%ld,%ld)%ld",&u,&v,&val);//这种字符输入最好 这样不好scanf("(%ld,%ld)%ld",&u,&v,&val); 这种可以 cin>>ch>>x>>ch>>y>>ch>>z; cap[u][v] += val; } while(fac--) { u = n; scanf("%s",str); sscanf(str,"(%ld)%ld",&v,&val);//scanf("(%ld)%ld",&v,&val); cap[u][v] += val; } while(cum--) { v = n+1; scanf("%s",str); sscanf(str,"(%ld)%ld",&u,&val); cap[u][v] += val; } long res = ek(n); cout< <