首页 > 代码库 > POJ1459 最大网络流
POJ1459 最大网络流
问题： POJ1459
涉及内容：最大网络流
分析：
本题问题看似非常复杂，实际上可以转化为单源点单汇点的最大网络流问题。
1）因为电量只在发电站产生，故增加源点S，构建从S到每个发电站的有向边，边的权值即各个发电站的发电量。则可把S看成唯一发电站，其余发电站只是一个中转站。
2）因为电量只在消费站消耗，故增加汇点T，构建从每个消费者到T的有向边，边的权值即各个消费者的耗电量。则可以把T看成唯一的消费站，其余消费者也作为中转站。
这样，问题就转化为从源点S到汇点T的最大网络流问题。可采用增广路径算法解决，耗时391ms。若采用的压入与重标记算法，或者重标记与前移算法，应该能达到更高的效率。
注：输入字符串处理的过程中，由于忽视了(u,v)z中的u,v,z可能大于一位的情况，导致wa了很久。
AC代码：
1 //Memory: 292K Time: 391MS 2 #include <iostream> 3 #include <cstring> 4 5 using namespace std; 6 7 const int maxn = 110; 8 int c[maxn][maxn]; 9 int cf[maxn][maxn]; 10 int p[maxn], cc[maxn]; 11 int n, np, nc, m; 12 int u, v, l; 13 int edge[maxn][maxn]; 14 int ne[maxn]; 15 int prior[maxn]; 16 char in[30]; 17 const int s = 101; 18 int q[maxn]; 19 int front, rear; 20 bool vis[maxn]; 21 int consume; 22 23 bool bfs( int s ) 24 { 25 for (int i = 0; i <= n; i++) 26 prior[i] = -1; 27 front = rear = 0; 28 q[rear++] = s; 29 while (front != rear) { 30 int current = q[front++]; 31 if ( cf[current][n] > 0 ) { 32 prior[n] = current; 33 return true;; 34 } 35 for (int i = 0; i < ne[current]; i++) { 36 if (cf[current][edge[current][i]] > 0 && edge[current][i] != current && prior[ edge[current][i] ] == -1 ) { 37 prior[ edge[current][i] ] = current; 38 q[rear++] = edge[current][i]; 39 } 40 } 41 } 42 return false; 43 } 44 45 void update() 46 { 47 int current; 48 int pr = n; 49 int _min = 1010; 50 while ( pr != s ) { 51 current = pr; 52 pr = prior[current]; 53 if ( cf[pr][current] < _min) 54 _min = cf[pr][current]; 55 } 56 current; 57 pr = n; 58 while (pr != s) { 59 current = pr; 60 pr = prior[current]; 61 cf[pr][current] -= _min; 62 cf[current][pr] += _min; 63 } 64 consume += _min; 65 } 66 67 void input() 68 { 69 memset(c, 0, sizeof(c)); 70 memset(edge, 0, sizeof(edge)); 71 memset(ne, 0, sizeof(ne)); 72 for (int i = 0; i < m; i++){ 73 scanf("%s", in); 74 int ix; 75 u = 0; 76 for (ix = 1; in[ix] != ‘,‘; ix++) 77 u = u * 10 + in[ix] - ‘0‘; 78 v = 0; 79 for (ix++; in[ix] != ‘)‘; ix++) 80 v = v * 10 + in[ix] - ‘0‘; 81 l = 0; 82 int len = strlen(in); 83 for (ix++; ix < len; ix++) { 84 l = l * 10 + in[ix] - ‘0‘; 85 } 86 c[u][v] = l; 87 edge[u][ne[u]++] = v; 88 } 89 for (int i = 0; i < np; i++) { 90 scanf("%s", in); 91 int ix; 92 u = 0; 93 for (ix = 1; in[ix] != ‘)‘; ix++) 94 u = u * 10 + in[ix] - ‘0‘; 95 l = 0; 96 int len = strlen(in); 97 for (ix++; ix < len; ix++) { 98 l = l * 10 + in[ix] - ‘0‘; 99 }100 c[s][u] = l;101 edge[s][ne[s]++] = u;102 }103 for (int i = 0; i < nc; i++) {104 scanf("%s", in);105 int ix;106 u = 0;107 for (ix = 1; in[ix] != ‘)‘; ix++)108 u = u * 10 + in[ix] - ‘0‘;109 l = 0;110 int len = strlen(in);111 for (ix++; ix < len; ix++) {112 l = l * 10 + in[ix] - ‘0‘;113 }114 c[u][n] = l;115 edge[u][ne[u]++] = n;116 }117 }118 int main()119 {120 while ( scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF ){121 input();122 memcpy(cf, c, sizeof(c));123 consume = 0;124 while ( bfs(s) ) {125 update();126 }127 printf("%d\n", consume);128 }129 return 0;130 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。