Power Network(网络流最大流)
Time Limit: 2000MS | Memory Limit: 32768K | |
Total Submissions: 24019 | Accepted: 12540 |
Description
An example is in figure 1. The label x/y of power station u shows that p(u)=x and pmax(u)=y. The label x/y of consumer u shows that c(u)=x and cmax(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and lmax(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6.
Input
Output
Sample Input
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20 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
Sample Output
15 6
Hint
Source
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 using namespace std; 5 #define MAXN 202 6 const int INT_MAX = 0x3f3f3f3f ; 7 int s, t; 8 int n, np, nc, m; 9 char str[50]; 10 int c[MAXN][MAXN]; 11 int f[MAXN][MAXN]; 12 int e[MAXN]; 13 int h[MAXN]; 14 void push(int u, int v) 15 { 16 int d = min(e[u], c[u][v] - f[u][v]); 17 f[u][v] += d; 18 f[v][u] = -f[u][v]; 19 e[u] -= d; 20 e[v] += d; 21 } 22 bool relabel(int u) 23 { 24 int mh = INT_MAX; 25 for(int i=0; i<n+2; i++) 26 { 27 if(c[u][i] > f[u][i]) 28 mh = min(mh, h[i]); 29 } 30 if(mh == INT_MAX) 31 return false; //残留网络中无从u出发的路 32 h[u] = mh + 1; 33 for(int i=0; i<n+2; i++) 34 { 35 if(e[u] == 0) //已无余流,不需再次push 36 break; 37 if(h[i] == mh && c[u][i] > f[u][i]) //push的条件 38 push(u, i); 39 } 40 return true; 41 } 42 void init_preflow() 43 { 44 memset(h, 0, sizeof(h)); 45 memset(e, 0, sizeof(e)); 46 h[s] = n+2; 47 for(int i=0; i<n+2; i++) 48 { 49 if(c[s][i] == 0) 50 continue; 51 f[s][i] = c[s][i]; 52 f[i][s] = -f[s][i]; 53 e[i] = c[s][i]; 54 e[s] -= c[s][i]; 55 } 56 } 57 void push_relabel() 58 { 59 init_preflow(); 60 bool flag = true; //表示是否还有relabel操作 61 while(flag) 62 { 63 flag = false; 64 for(int i=0; i<n; i++) 65 if(e[i] > 0) 66 flag = flag || relabel(i); 67 } 68 } 69 int main() 70 { 71 while(scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF) 72 { 73 s = n; t = n+1; 74 memset(c, 0, sizeof(c)); 75 memset(f, 0, sizeof(f)); 76 while(m--) 77 { 78 scanf("%s", &str); 79 int u=0, v=0, z=0; 80 sscanf(str, "(%d,%d)%d", &u, &v, &z); 81 c[u][v] = z; 82 } 83 for(int i=0; i<np+nc; i++) 84 { 85 scanf("%s", &str); 86 int u=0, z=0; 87 sscanf(str, "(%d)%d", &u, &z); 88 if(i < np) 89 c[s][u] = z; 90 else if(i >= np && i < np + nc) 91 c[u][t] = z; 92 } 93 push_relabel(); 94 printf("%d\n", e[t]); 95 } 96 }
dinic递归 110ms / 非递归 110 或 94 ms:http://hefeijack.iteye.com/blog/1885944
dinic 63ms/SAP 63 ms:http://www.cnblogs.com/kuangbin/archive/2012/09/11/2680908.html
dinic 63ms :http://blog.csdn.net/u011721440/article/details/38611197
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。