学习网络流中的最大流，自然要先学会基础的最大流算法。这里参考学习挑战写了两个测试代码，学习了通过寻找增广路计算最大流。
1 /* Ford_Fulkerson算法 2 *进行f（最大流）次dfs()， 3 * O(f|E|) 4 */ 5 #include <bits/stdc++.h> 6 using namespace std; 7 const int INF = 0x3f3f3f3f; 8 const int max_V = 1010; 9 struct Edge{ //终点，容量， 反向边 10 int to, cap, rev; 11 }; 12 vector<Edge> G[max_V]; //邻接表建图 13 bool used[max_V]; //dfs()用到的访问标记 14 int n, k; 15 void add_edge(int from, int to, int cap){ 16 G[from].push_back(Edge{to, cap, G[to].size()}); 17 G[to].push_back(Edge{from, 0, G[from].size() - 1}); 18 } 19 int dfs(int v, int t, int f){ 20 if(v == t) return f; 21 used[v] = true; 22 for(int i = 0; i<G[v].size(); i++){ 23 Edge &e = G[v][i]; 24 if(!used[e.to] && e.cap>0){ 25 int d = dfs(e.to, t, min(f, e.cap)); 26 if(d > 0){ 27 e.cap -= d; 28 G[e.to][e.rev].cap += d; 29 return d; 30 } 31 } 32 } 33 return 0; 34 } 35 int cnt; 36 int max_flow(int s, int t){ 37 int flow = 0; 38 while(true){ 39 memset(used, 0, sizeof(used)); 40 int f = dfs(s, t, INF); 41 42 printf("残余网络上的增广路--------- %d ", ++cnt); 43 for(int i=0; i<=n; i++){ 44 for(int j=0; j<G[i].size(); j++){ 45 printf("[%d %d %d %d]%s", i, G[i][j].to, G[i][j].cap, G[i][j].rev, j==(G[i].size()-1)?" ":" "); 46 } 47 } 48 49 if(f == 0){ 50 return flow; 51 } 52 flow += f; 53 } 54 } 55 int main(){ 56 freopen("in.txt", "r", stdin); 57 58 for(int i=0; i<n; i++){ 59 G[i].clear(); 60 } 61 scanf("%d%d", &n, &k); 62 for(int i=0; i<k; i++){ 63 int fr, to, ca; 64 scanf("%d%d%d",&fr, &to, &ca); 65 add_edge(fr, to, ca); 66 } 67 for(int i=0; i<=n; i++){ 68 for(int j=0; j<G[i].size(); j++){ 69 printf("[%d %d %d %d]%s", i, G[i][j].to, G[i][j].cap, G[i][j].rev, j==(G[i].size()-1)?" ":" "); 70 } 71 } 72 cout << endl; 73 printf("%d ", max_flow(1, n)); 74 return 0; 75 } 76
1 /* 2 * Dinic算法 3 * O(|E||V^2|) 4 */ 5 #include <bits/stdc++.h> 6 using namespace std; 7 const int INF = 0x3f3f3f3f; 8 const int max_V = 1010; 9 struct Edge{ //终点，容量， 反向边 10 int to, cap, rev; 11 }; 12 vector<Edge> G[max_V]; 13 int level[max_V]; //顶点到原点的距离标号 14 int iter[max_V]; //当前弧，在其之前的边无用 15 int n, k; 16 void add_edge(int from, int to, int cap){ 17 G[from].push_back( (Edge){to, cap, G[to].size()} ); 18 G[to].push_back((Edge){from, 0, G[from].size()-1}); //G[from].size()-1: 为to->from的反向边编号，即边(from->to)的编号 19 } 20 /* 21 * 通过bfs()计算从源点出发的距离标号 22 */ 23 void bfs(int s){ 24 memset(level, -1, sizeof(level)); 25 queue<int> que; 26 level[s] = 0; 27 que.push(s); 28 while(!que.empty()){ 29 int v = que.front(); que.pop(); 30 for(int i=0; i<G[v].size(); i++){ 31 Edge &e = G[v][i]; 32 if(e.cap > 0 && level[e.to] < 0){ 33 level[e.to] = level[v] + 1; 34 que.push(e.to); 35 } 36 } 37 } 38 } 39 /* 40 * dfs()寻找增广路 41 */ 42 int dfs(int v, int t, int f){ 43 if(v == t) return f; 44 for(int &i = iter[v]; i < G[v].size(); i++){ 45 Edge &e = G[v][i]; 46 if(e.cap > 0 && level[v] < level[e.to]){ 47 //level[e.to] == level[v] - 1 48 int d = dfs(e.to, t, min(f, e.cap)); 49 if(d > 0){ 50 e.cap -= d; 51 G[e.to][e.rev].cap += d; 52 return d; 53 } 54 } 55 } 56 return 0; 57 } 58 /* 59 * 求s到t的最大流 60 */ 61 int cnt; /// 62 int max_flow(int s, int t){ 63 int flow = 0; 64 while(true){ 65 bfs(s); 66 if(level[t] < 0) return flow; 67 memset(iter, 0, sizeof(iter)); 68 int f; 69 while((f = dfs(s, t, INF)) > 0){ 70 flow += f; 71 } 72 printf("残余网络上的增广路--------- %d ", ++cnt); 73 for(int i=0; i<=n; i++){ 74 for(int j=0; j<G[i].size(); j++){ 75 printf("[%d %d %d %d]%s", i, G[i][j].to, G[i][j].cap, G[i][j].rev, j==(G[i].size()-1)?" ":" "); 76 } 77 } 78 79 } 80 } 81 int main(){ 82 freopen("in.txt", "r", stdin); 83 84 for(int i=0; i<n; i++){ 85 G[i].clear(); 86 } 87 scanf("%d%d", &n, &k); 88 for(int i=0; i<k; i++){ 89 int fr, to, ca; 90 scanf("%d%d%d",&fr, &to, &ca); 91 add_edge(fr, to, ca); 92 } 93 for(int i=0; i<=n; i++){ 94 for(int j=0; j<G[i].size(); j++){ 95 printf("[%d %d %d %d]%s", i, G[i][j].to, G[i][j].cap, G[i][j].rev, j==(G[i].size()-1)?" ":" "); 96 } 97 } 98 cout << endl; 99 printf("%d ", max_flow(1, n)); 100 return 0; 101 }
这篇文章对一些概念铺垫的很详细：网络流(一) 入门到熟练
A - A Plug for UNIX
题意：
n种插座各一个接在电源上，
m个用电器，每个用电器有一个插座类型，
k种转换器，可以将一种类型转换为另一种。每种转换器可以用无数个。
问最少有多少用电器不能用。
Thinking：
- 注意转换器第一个数字是插座类型，提供给用电器，第二个数字是插头类型，提供给插座。
- 这里重点是把题目抽象为网络流的最大流问题，题说最少多少电器不能用，则思考最多多少电器能用。难点是如何建图。
- 建图：源点到每个插座连一条容量为1的边， 每个插座向每个类型相同的用电器连一条容量为1的边， 每个用电器向汇点连一条容量为1的边，转换器依题目定义连一条INF的边。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <map> 5 #include <vector> 6 #include <queue> 7 #include <string> 8 using namespace std; 9 const int INF = 0x3f3f3f3f; 10 const int maxn = 820; 11 struct edge{ 12 int to, cap, rev; 13 }; 14 vector<edge> G[maxn]; 15 int level[maxn]; 16 int iter[maxn]; 17 void add_edge(int from, int to, int cap){ 18 G[from].push_back((edge){to, cap, G[to].size()}); 19 G[to].push_back((edge){from, 0, G[from].size()-1}); 20 } 21 //submit时修改下这里，poj不支持这种写法 22 void bfs(int s){ 23 memset(level, -1, sizeof(level)); 24 queue<int> que; 25 level[s] = 0; 26 que.push(s); 27 while(!que.empty()){ 28 int v = que.front(); que.pop(); 29 for(int i=0; i<G[v].size(); i++){ 30 edge &e = G[v][i]; 31 if(e.cap > 0 && level[e.to] < 0){ 32 level[e.to] = level[v] + 1; 33 que.push(e.to); 34 } 35 } 36 } 37 } 38 int dfs(int v, int t, int f){ 39 if(v == t) return f; 40 for(int &i = iter[v]; i<G[v].size(); i++){ 41 edge &e = G[v][i]; 42 if(e.cap > 0 && level[e.to]>level[v]){ 43 int d = dfs(e.to, t, min(f, e.cap)); 44 if(d > 0){ 45 e.cap -= d; 46 G[e.to][e.rev].cap += d; 47 return d; 48 } 49 } 50 } 51 return 0; 52 } 53 int max_flow(int s, int t){ 54 int flow = 0; 55 while(true){ 56 bfs(s); 57 if(level[t] < 0) return flow; 58 memset(iter, 0, sizeof(iter)); 59 int f; 60 while((f = dfs(s, t, INF)) > 0) flow += f; 61 } 62 } 63 char str[30], stmp[30]; 64 int cnt; 65 map<string, int> rec; 66 int n, m, k; 67 void init(){ 68 for(int i=0; i<n; i++){ 69 G[i].clear(); 70 } 71 rec.clear(); 72 cnt = 3; 73 } 74 int need[maxn]; 75 int main(){ 76 freopen("in.txt", "r", stdin); 77 while(scanf("%d", &n) != EOF){ 78 init(); 79 int s = 1, t = 2; 80 ///// 81 /////建图是重点 82 ///// 83 /* 84 * 源点指向插座，容量为1 85 */ 86 for(int i=0; i<n; i++){ 87 str[0] = ' '; 88 scanf("%s", str); 89 rec[str] = cnt++; 90 add_edge(s, rec[str], 1); 91 } 92 /* 93 *插头(str)向其对应的用电器(stmp)指，容量为1 94 *所有用电器指向源点s，容量为1 95 */ 96 scanf("%d", &m); 97 for(int i=0; i<m; i++){ 98 stmp[0] = str[0] = ' '; 99 scanf("%s%s",stmp, str); 100 if(rec.find(str) == rec.end()){ 101 rec[str] = cnt++; 102 } 103 if(rec.find(stmp) == rec.end()){ 104 rec[stmp] = cnt++; 105 } 106 add_edge(rec[stmp], t, 1); 107 add_edge(rec[str], rec[stmp], 1); 108 } 109 /* 110 * 可以通过适配器相连的两个插座s1,s2，s2->s1 111 * 其值为INF 112 */ 113 scanf("%d", &k); 114 for(int i=0; i<k; i++){ 115 stmp[0] = str[0] = ' '; 116 scanf("%s%s",stmp, str); 117 if(rec.find(str) == rec.end()){ 118 rec[str] = cnt++; 119 } 120 if(rec.find(stmp) == rec.end()){ 121 rec[stmp] = cnt++; 122 } 123 add_edge(rec[str], rec[stmp], INF); 124 } 125 /* 126 for(int i=0; i<cnt; i++){ 127 for(int j=0; j<G[i].size(); j++){ 128 printf("[%d %d %d %d]%s", i, G[i][j].to, G[i][j].cap, G[i][j].rev, j==(G[i].size()-1)?" ":" "); 129 } 130 } 131 cout << endl; 132 */ 133 printf("%d ", m - max_flow(s,t)); 134 } 135 return 0; 136 }
B - Power Network
题意：一个电力网络，一共n个节点，m条边，np个发电站，nc个用户。每条边有一个容量，每个发电站有一个最大负载，每一个用户也有一个最大接受量。问最多能供给多少电力。
Thinking:
属于多个源点和汇点的情况，设一个超级源点，与每一个源点连一条容量为最大负载的边，设一个超级汇点，每一个用户与超级汇点连一条容量为最大接受量的边，然后求最大流。
这里暴露的问题：
- init()函数里用n初始化了，应用maxn。教训：初始化尽量大。
- 输入有问题，这里用了cin，可以避免空格的问题。poj discuss里有推荐用scanf()，比cin快了好多。
1 while(scanf("%c", &tmp)){ 2 if(tmp == '('){ 3 scanf("%d,%d)%d", &u, &v, &z); 4 break; 5 } 6 }
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <map> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 using namespace std; 10 const int INF = 0x3f3f3f3f; 11 const int maxn = 500; 12 struct edge{ 13 int to, cap, rev; 14 }; 15 vector<edge> G[maxn]; 16 int level[maxn]; 17 int iter[maxn]; 18 void add_edge(int from, int to, int cap){ 19 G[from].push_back((edge){to, cap, G[to].size()}); 20 G[to].push_back((edge){from, 0, G[from].size()-1}); 21 } 22 //submit时修改下这里，poj不支持这种写法 23 void bfs(int s){ 24 memset(level, -1, sizeof(level)); 25 queue<int> que; 26 level[s] = 0; 27 que.push(s); 28 while(!que.empty()){ 29 int v = que.front(); que.pop(); 30 for(int i=0; i<G[v].size(); i++){ 31 edge &e = G[v][i]; 32 if(e.cap > 0 && level[e.to] < 0){ 33 level[e.to] = level[v] + 1; 34 que.push(e.to); 35 } 36 } 37 } 38 } 39 int dfs(int v, int t, int f){ 40 if(v == t) return f; 41 for(int &i = iter[v]; i<G[v].size(); i++){ 42 edge &e = G[v][i]; 43 if(e.cap > 0 && level[e.to]>level[v]){ 44 int d = dfs(e.to, t, min(f, e.cap)); 45 if(d > 0){ 46 e.cap -= d; 47 G[e.to][e.rev].cap += d; 48 return d; 49 } 50 } 51 } 52 return 0; 53 } 54 int max_flow(int s, int t){ 55 int flow = 0; 56 while(true){ 57 bfs(s); 58 if(level[t] < 0) return flow; 59 memset(iter, 0, sizeof(iter)); 60 int f; 61 while((f = dfs(s, t, INF)) > 0) flow += f; 62 } 63 } 64 void init(){ 65 for(int i=0; i<maxn; i++){ 66 G[i].clear(); 67 } 68 } 69 int main(){ 70 freopen("in.txt", "r", stdin); 71 int n, m, np, nc; 72 while(cin >> n >> np >> nc >> m){ 73 init(); 74 ///// 75 /////建图是重点 76 ///// 77 int u, v, z; 78 char tmp; 79 /* 80 * power stations连接 consumers 81 * 容量为 l(u,v) 82 */ 83 for(int i = 0; i < m; i++){ 84 cin >> tmp >> u >> tmp >> v >> tmp >> z; 85 // printf("%d %d %d ", u, v, z); 86 if(u == v){ 87 continue; 88 /* 89 *一个顶点上的环不影响最终结果 90 *环：一旦u到v后，level数组会标记u，环将无用 91 */ 92 } 93 u++, v++; 94 add_edge(u, v, z); 95 } 96 int s = n+1, t = n+2; 97 /* 98 * 超级源点s连接 power stations 99 * 容量为p(u) 100 */ 101 for(int i=0; i<np; i++){ 102 cin >> tmp >> u >> tmp >> z; 103 // printf("%d %d ", u, z); 104 u++; 105 add_edge(s, u, z); 106 } 107 /* 108 * consumers连接超级汇点 t 109 * 容量为c(u) 110 */ 111 for(int i=0; i<nc; i++){ 112 cin >> tmp >> u >> tmp >> z; 113 // printf("%d %d ", u, z); 114 u++; 115 add_edge(u, t, z); 116 } 117 /* 118 for(int i=0; i<=t; i++){ 119 for(int j=0; j<G[i].size(); j++){ 120 printf("[%d %d %d %d]%s", i, G[i][j].to, G[i][j].cap, G[i][j].rev, j==(G[i].size()-1)?" ":" "); 121 } 122 } 123 cout << endl; 124 */ 125 printf("%d ", max_flow(s,t)); 126 } 127 return 0; 128 }
C - Ombrophobic Bovines
题意：
有F[1,200]块田地，每块地给出cows的初始值和最终可容纳值[1,1000]，集合数量为P[1,1500]的边集（The paths are wide, so that any number of cows can traverse a path in either direction.）注意是双向。求下雨前最短的时间拉警报，使每头牛都可以到达避难所，若所有奶牛都无法进入避难所，则输出-1。
（感觉每次把题目描述一遍比较好，因为团体赛，和队友交流题意时，感觉彼此都有点儿懵，就当锻炼描述题意能力了）
Thinking:
逆着思考，二分答案mid，拆点构建模型，【一般不光边上有容量限制顶点上也有容量限制的情况需要拆点】，这里需要想清楚拆的两点代表什么，怎样与源、汇点相连，因为这决定了如何建田地之间的边，这里建边i->j'，可以理解为I的出cow点i到J的收cow点j'，容量为无限大，如果其距离小于二分答案。
这里暴露的问题：
- 这里有一个技巧，关于二分时r的设置可以参考poj中的discuss，感觉那里高人好多。
- 路径是双向的。
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <map> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 using namespace std; 10 #define LL long long 11 const LL INFL = 1e16; 12 const int INF = 0x3f3f3f3f; 13 const int maxn = 500; 14 struct edge{ 15 int to, cap, rev; 16 edge(){} 17 edge(int a, int b, int c) : to(a), cap(b), rev(c){} 18 }; 19 vector<edge> G[maxn]; 20 int level[maxn]; 21 int iter[maxn]; 22 void add_edge(int from, int to, int cap){ 23 G[from].push_back(edge(to, cap, G[to].size())); 24 G[to].push_back(edge(from, 0, G[from].size()-1)); 25 } 26 void bfs(int s){ 27 memset(level, -1, sizeof(level)); 28 level[s] = 0; 29 queue<int> que; 30 que.push(s); 31 while(!que.empty()){ 32 int v = que.front(); que.pop(); 33 for(int i=0; i<G[v].size(); i++){ 34 edge &e = G[v][i]; 35 if(e.cap>0 && level[e.to]<0){ 36 level[e.to] = level[v] + 1; 37 que.push(e.to); 38 } 39 } 40 } 41 } 42 int dfs(int v, int t, int f){ 43 if(v == t) return f; 44 for(int &i = iter[v]; i<G[v].size(); i++){ 45 edge &e = G[v][i]; 46 if(e.cap>0 && level[e.to]>level[v]){ 47 int d = dfs(e.to, t, min(e.cap, f)); 48 if(d > 0){ 49 e.cap -= d; 50 G[e.to][e.rev].cap += d; 51 return d; 52 } 53 } 54 } 55 return 0; 56 } 57 int max_flow(int s, int t){ 58 int flow = 0; 59 while(true){ 60 bfs(s); 61 if(level[t] < 0) return flow; 62 memset(iter, 0, sizeof(iter)); 63 int f; 64 while((f=dfs(s, t, INF)) > 0) flow += f; 65 } 66 } 67 LL dist[maxn][maxn]; 68 void floyd(int n){ 69 for(int k=1; k<=n; k++){ 70 for(int i=1; i<=n; i++){ 71 for(int j=1; j<=n; j++){ 72 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 73 } 74 } 75 } 76 } 77 int init_cows[maxn], hold_cows[maxn]; 78 void buildG(LL mid, int n, int s, int t){ 79 for(int i=0; i<maxn; i++){ 80 G[i].clear(); 81 } 82 for(int i=1; i<=n; i++){ 83 add_edge(s, i, init_cows[i]); 84 add_edge(i+n, t, hold_cows[i]); 85 add_edge(i, i+n, INF); 86 } 87 /* 88 * 拆点 89 * 怎么确定出入顺序 90 * 这里是建图的重点 91 * 可以理解为从 i的出牛点 到 j收牛点 可以有INF的容量 92 */ 93 for(int i=1; i<=n; i++){ 94 for(int j=i+1; j<=n; j++){ 95 if(dist[i][j] <= mid){ 96 add_edge(i, j+n, INF); 97 add_edge(j, i+n, INF); 98 } 99 } 100 } 101 } 102 int main(){ 103 // freopen("in.txt", "r", stdin); 104 int n, m; 105 while(scanf("%d%d", &n, &m) != EOF){ 106 int s = 0, t = 2*n+1, sum = 0; 107 for(int i=1; i<=n; i++){ 108 scanf("%d%d", &init_cows[i], &hold_cows[i]); 109 sum += init_cows[i]; 110 } 111 for(int i=1; i<=n; i++) 112 for(int j=1; j<=n; j++) 113 dist[i][j] = INFL; 114 /* 这里是求解的重点 二分的运用+如何将问题转换为最大流 115 * ？？？？为什么这么思考我还是没想通， 116 * floyd()求得任意两点间的最短路径， 117 * 然后二分答案 118 * 判断是否可以在mid的距离(时间)内完成移动 119 * 即max_flow() >= sum 120 */ 121 LL l = 0, r = 1, ans = -1; 122 /* 123 * 这里关于r的优化方法是看的poj discuss，发现里面很多讨论还是很独到的。 124 * 最开始我设置了 "how long any cow takes to traverse it "的最大值 与 P的最大值的积 125 * 即1e9 * 1500 * 10, 显然时间快了200-350 126 */ 127 for(int i=0; i<m; i++){ 128 int x, y; 129 LL val; 130 scanf("%d%d%lld", &x, &y, &val); 131 if(val < dist[x][y]) 132 dist[y][x] = dist[x][y] = val; 133 //这里路径是双向的 134 r += val; 135 } 136 floyd(n); 137 while(l <= r){ 138 LL mid = (l+r)/2; 139 buildG(mid, n, s, t); 140 int tmp = max_flow(s, t); 141 if(tmp >= sum){ 142 ans = mid; 143 r = mid -1; 144 }else{ 145 l = mid + 1; 146 } 147 } 148 /* 149 for(int i=0; i<=t; i++){ 150 for(int j=0; j<G[i].size(); j++){ 151 printf("[%d %d %d %d]%s", i, G[i][j].to, G[i][j].cap, G[i][j].rev, j==(G[i].size()-1)?" ":" "); 152 } 153 } 154 cout << endl; 155 */ 156 printf("%lld ", ans); 157 } 158 return 0; 159 }
D - Secret Milking Machine
题意：
N(2,200)个landmarks，P(1,40000)条bidirectional trails(双向路径)，从1到N，使T条不同的路径中所有边中最长的边最小，注意不是边之和路径最小，而是边最小。
Thinking:
- 因为T条路径不存在同边，显然这里建图时符合条件的边的容量为1（保证不同路径不会同边），其余为0，回边与边的容量相同。
- 二分答案（边的长度），按1的思路建图，条件显然为边长小于mid时cap为1。然后求最大流，看是否有T条路径。
注意：图中有平行边和重边，这个不能随便处理，因为是求解最大边的最小值。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 using namespace std; 7 #define LL long long 8 const int INF = 0x3f3f3f3f; 9 const int maxn = 410, maxp = 40010; 10 struct edge{ 11 int to, cap, rev; 12 edge(){} 13 edge(int a, int b, int c) : to(a), cap(b), rev(c) {} 14 }; 15 vector<edge> G[maxn]; 16 int level[maxn], iter[maxn]; 17 void add_edge(int from, int to, int cap){ 18 G[from].push_back(edge(to, cap, G[to].size())); 19 G[to].push_back(edge(from, cap, G[from].size()-1)); 20 } 21 void bfs(int s){ 22 memset(level, -1, sizeof(level)); 23 level[s] = 0; 24 queue<int> que; 25 que.push(s); 26 while(!que.empty()){ 27 int v = que.front(); que.pop(); 28 for(int i=0; i<G[v].size(); i++){ 29 edge &e = G[v][i]; 30 if(e.cap > 0 && level[e.to] < 0){ 31 level[e.to] = level[v] + 1; 32 que.push(e.to); 33 } 34 } 35 } 36 } 37 int dfs(int v, int t, int f){ 38 if(v == t) return f; 39 for(int &i = iter[v]; i < G[v].size(); i++){ 40 edge &e = G[v][i]; 41 if(e.cap > 0 && level[e.to] > level[v]){ 42 int d = dfs(e.to, t, min(f, e.cap)); 43 if(d > 0){ 44 e.cap -= d; 45 G[e.to][e.rev].cap += d; 46 return d; 47 } 48 } 49 } 50 return 0; 51 } 52 int max_flow(int s, int t){ 53 int flow = 0; 54 while(true){ 55 bfs(s); 56 if(level[t] < 0) return flow; 57 memset(iter, 0, sizeof(iter)); 58 int f; 59 while( (f = dfs(s, t, INF)) > 0){ 60 flow += f; 61 } 62 } 63 } 64 int A[maxp], B[maxp], L[maxp]; 65 void buildG(int n, int mid){ 66 for(int i=0; i<maxn; i++) G[i].clear(); 67 for(int i=0; i<n; i++){ 68 if(L[i] <= mid){ 69 add_edge(A[i], B[i], 1); 70 } 71 } 72 } 73 int main(){ 74 // freopen("in.txt", "r", stdin); 75 int n, p, t; 76 while( scanf("%d%d%d", &n, &p, &t) != EOF ){ 77 /* 78 * discuss里说这里取上界可能会超时 79 * 关于二分的l,r取值不能太随便 80 */ 81 int l = INF, r = 0; 82 /* 83 * 注意这里有平行边 84 * 想了想，这里不能随便处理，因为二分的是 最长 边的 最小 值 85 */ 86 for(int i=0; i<p; i++){ 87 scanf("%d%d%d", &A[i], &B[i], &L[i]); 88 l = min(l, L[i]); 89 r = max(r, L[i]); 90 } 91 int ans = -1; 92 while(l <= r){ 93 int mid = (l + r)/2; 94 buildG(p, mid); 95 if(max_flow(1, n) >= t){ 96 ans = mid; 97 r = mid - 1; 98 }else{ 99 l = mid + 1; 100 } 101 } 102 printf("%d ", ans); 103 } 104 return 0; 105 }
下面题目是有关最小费用最大流。
这里放上文章，但还未细看。1、最小费用最大流(详解+模板) 2、最详细网络流建模基础
E - Farm Tour
题意：农场N[1,1000]块地，M[1,10000]条双向道路，ai-->bi,长ci，问从1-->N，再从N-->1，往返道路无同边，求总长度最短。
Thinking:
这里建图与D题有异曲同工之处，因为是来回不同边，所以可以视为从1-->N最大流为2，且每条边容量为1。然后求最小费用流。
这里代码是学习挑战这本书的，还不是很理解这个算法，回头再看。
1 #include <cstdio> 2 #include <algorithm> 3 #include <vector> 4 #include <cstring> 5 using namespace std; 6 #define LL long long 7 const int INF = 0x3f3f3f3f; 8 const int maxn = 1010; 9 struct edge{ 10 int to, cap, cost, rev; 11 edge(int a, int b, int c, int d) : to(a), cap(b), cost(c), rev(d){} 12 }; 13 int V; //顶点数 14 vector<edge> G[maxn]; 15 int dist[maxn]; //最短距离 16 int prevv[maxn], preve[maxn]; //最短路的前驱结点和对应的边 17 void add_edge(int from, int to, int cap, int cost){ 18 G[from].push_back(edge(to, cap, cost, G[to].size())); 19 G[to].push_back(edge(from, 0, -cost, G[from].size()-1)); 20 } 21 //求解从s到t流量为f的最小费用流 22 //如果不能再增广，返回-1 23 int min_cost_flow(int s, int t, int f){ 24 int res = 0; 25 while(f > 0){ 26 fill(dist, dist+V, INF); 27 dist[s] = 0; 28 bool update = true; 29 while(update){ 30 update = false; 31 for(int v = 0; v < V; v++){ 32 if(dist[v] == INF){ 33 continue; 34 } 35 for(int i = 0; i < G[v].size(); i++){ 36 edge &e = G[v][i]; 37 if(e.cap > 0 && dist[e.to] > dist[v]+e.cost){ 38 dist[e.to] = dist[v] + e.cost; 39 prevv[e.to] = v; 40 preve[e.to] = i; 41 update = true; 42 } 43 } 44 } 45 } 46 if(dist[t] == INF){ 47 return -1; 48 }//不能增广 49 //沿s->t的最短路尽量增广 50 int d = f; 51 for(int v = t; v != s; v = prevv[v]){ 52 d = min(d, G[prevv[v]][preve[v]].cap); 53 } 54 f -= d; 55 res += d * dist[t]; 56 for(int v = t; v != s; v=prevv[v]){ 57 edge &e = G[prevv[v]][preve[v]]; 58 e.cap -= d; 59 G[v][e.rev].cap += d; 60 } 61 } 62 return res; 63 } 64 int main(){ 65 // freopen("in.txt", "r", stdin); 66 int n, m; 67 while( scanf("%d%d", &n, &m) != EOF ){ 68 for(int i=0; i<maxn; i++){ 69 G[i].clear(); 70 } 71 for(int i = 0; i < m; i++){ 72 int x, y, z; 73 scanf("%d%d%d", &x, &y, &z); 74 add_edge(x-1, y-1, 1, z); 75 add_edge(y-1, x-1, 1, z); 76 } 77 int s = 0, t = n-1; 78 V = n; 79 printf("%d ", min_cost_flow(s, t, 2)); 80 } 81 return 0; 82 }