链接：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1459题意 ：有一个电力网络，有发电厂，有变压器，又用户，图的意思是容量，以及流量，还有边，以及边的容量，流量。求解用户的最大使用量。
输入 ：2个测试数据
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
//总共两个点 一个发电厂，一个用户，2条边，(0, 1)点容量为20，(1， 0)点容量为10，编号为0的点是发电厂，即源，编号为1的点是用户，即汇
7 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
//意思同上
想法 ：
这个题就是一个单纯的不能再单纯的网络流了，锻炼了一下英语能力。设一个源s和一个汇t，我设的是第m个点位源，第m + 1个点位汇。最后把源s和发电厂连接，边的容量为发电厂的容量，将用户与汇t连接，容量为用户的容量
然后fm最大流 ：不断找源s和汇t的路径，选取瓶颈容两，更新剩余图，直至不能更新。剩余容量和为结果。时间复杂度比较高。望高手指点更好的算法。
代码如下 ：
1 #include <stdio.h>
2 #include <string.h>
3 #include <queue>
4 #define max 500
5 using namespace std;
6 int n, np, nc, m, r[max][max], ok, judge[max], p[max], res;
7 queue<int> qu, qq;
8 void gao(){
9 int i, j, s, t;
10 qu.push(n);
11 judge[n] = 1;
12 while(1){
13 s = qu.size();
14 if(!s){ok = 0;return;}
15 while(s--){
16 t = qu.front();
17 qu.pop();
18 if(t == n + 1){ok = 1;return;}
19 for(i = 0; i <= n + 1; i++){
20 if(r[t][i] > 0 && !judge[i]){
21 qu.push(i);
22 judge[i] = 1;
23 p[i] = t;
24 }
25 }
26 }
27 }
28 }
29 void update(){
30 int i, j, u, v, min = 999999999;
31 u = p[n + 1];
32 v = n + 1;
33 while(u >= 0){
34 if(r[u][v] < min)min = r[u][v];
35 v = u;
36 u = p[u];
37 }
38 u = p[n + 1];
39 v = n + 1;
40 while(u >= 0){
41 r[u][v] -= min;
42 r[v][u] += min;
43 v = u;
44 u = p[u];
45 }
46 res += min;
47 }
48 int main(){
49 freopen("1459.in","r",stdin);
50 freopen("1459.out","w",stdout);
51 int i, j, u, v, w;char c;
52 while(scanf("%d%d%d%d", &n, &np, &nc, &m) != -1){
53 ok = 1;res = 0;
54 memset(r, 0, sizeof(r));
55 for(i = 0; i < m; i++){
56 while(getchar()!='(');
57 scanf("%d,%d)%d", &u, &v, &w);
58 r[u][v] = w;
59 }
60 for(i = 0; i < np; i++){
61 while(getchar()!='(');
62 scanf("%d)%d", &u, &w);
63 r[n][u] = w;
64 }
65 for(i = 0; i < nc; i++){
66 while(getchar()!='(');
67 scanf("%d)%d", &u, &w);
68 r[u][n + 1] = w;
69 }
70 while(ok){
71 ok = 0;qu = qq;
72 memset(p, -1, sizeof(p));
73 memset(judge, 0, sizeof(judge));
74 gao();
75 if(ok)
76 update();
77 }
78 printf("%d\n", res);
79 }
80 return 0;
81 }
82
83
ps ： 输入搞了我几次re，比较有意思。