首页 > 代码库 > 上下界网络流小结
上下界网络流小结
虽然网上已经有很详细的解释了，但是别人总结的终究是别人的。
1无源无汇上下界的可行流
首先明确定义：B[u, v]和C[u, v]表示边(u,v)的下界容量和上界容量，我们的问题是求一个每条边都具有上下界的可行流。
简单分析：由于每条边要满足下界容量，而且每个点要满足流量平衡，所以就需要对平时的网络流模型改造。
方法一：建立附加远点回电，S，T，对于边(u, v)，连边S->v,容量B[u, v], 及u->T, 容量B[u, v], 然后对于本来的边u->v,容量改为C[u, v]-B[u, v]，这样对于u，v都可以看做与原来的图等效了，做网络流之后，如果存在可行解，那么S出发的边全部满流。
方法二：sum[u],表示进入u的下界容量之后，sum[u] = sigma{B[i, u]}-sigma{B[u, j]},F[u, v]为实际流过(u, v)的容量，
若sum[u] > 0, 连S->u的边容量为sum[u]；
若sum[u] < 0, 连u->T的边容量为-sum[u]。
ZOJ - 2314
Reactor Cooling
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pb push_back 9 #define in freopen("solve_in.txt", "r", stdin); 10 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 11 #define inf 0x0f0f0f0f 12 using namespace std; 13 typedef long long LL; 14 typedef map<int, int> MPS; 15 typedef pair<int, int> PII; 16 const int maxn = 222; 17 struct Node { 18 int c, l, id; 19 Node() {} 20 Node(int c, int l, int id):c(c), l(l), id(id) {} 21 }; 22 vector<Node> cap; 23 24 25 struct Edge { 26 int u, v, c; 27 Edge(int u, int v, int c):u(u), v(v), c(c) {} 28 }; 29 struct Max_flow { 30 int n, m; 31 int src, sink; 32 vector<Edge> edges; 33 vector<int> G[maxn]; 34 int Now[maxn], Dfn[maxn], cur[maxn]; 35 void init(int n) { 36 this->n = n; 37 for(int i = 0; i < n; i++) G[i].clear(); 38 edges.clear(); 39 } 40 void add(int u, int v, int c) { 41 edges.pb(Edge(u, v, c)); 42 edges.pb(Edge(v, u, 0)); 43 m = edges.size(); 44 G[u].pb(m-2); 45 G[v].pb(m-1); 46 } 47 int ISAP(int s, int flow) { 48 if(s == sink) 49 return flow; 50 int i, tab = n, vary, now = 0; 51 int p = cur[s]; 52 do { 53 Edge &e = edges[G[s][cur[s]]]; 54 if(e.c > 0) { 55 if(Dfn[s] == Dfn[e.v]+1) 56 vary = ISAP(e.v, min(flow-now, e.c)), 57 now += vary, e.c -= vary, edges[G[s][cur[s]]^1].c += vary; 58 if(Dfn[src] == n) 59 return now; 60 if(e.c > 0) tab = min(tab, Dfn[e.v]); 61 if(flow == now) 62 break; 63 } 64 cur[s]++; 65 if(cur[s] == (int)G[s].size()) cur[s] = 0; 66 } while(p != cur[s]); 67 if(now == 0) { 68 if(--Now[Dfn[s]] == 0) 69 Dfn[src] = n; 70 Now[Dfn[s] = tab+1]++; 71 } 72 return now; 73 } 74 int max_flow(int src, int sink) { 75 this->src =http://www.mamicode.com/ src; 76 this->sink = sink; 77 int flow = 0; 78 memset(Dfn, 0, sizeof Dfn); 79 memset(Now, 0, sizeof Dfn); 80 memset(cur, 0, sizeof cur); 81 Now[0] = n; 82 for(; Dfn[src] < n;) 83 flow += ISAP(src, inf); 84 return flow; 85 } 86 } mc; 87 vector<int> mx; 88 89 int main() { 90 91 int T; 92 for(int t = scanf("%d", &T); t <= T; t++) { 93 int n, m; 94 cap.clear(); 95 mx.clear(); 96 int ff = 0; 97 scanf("%d%d", &n, &m); 98 mc.init(n+2); 99 int src = http://www.mamicode.com/n, sink = n+1;100 101 for(int i = 1; i <= m; i++) {102 int u, v, c, l;103 scanf("%d%d%d%d", &u, &v, &l, &c);104 ff += l;105 u--, v--;106 mc.add(u, v, c-l);107 int tmp = mc.edges.size()-2;108 cap.pb(Node(c, l, tmp));109 mc.add(src, v, l);110 tmp = mc.edges.size()-2;111 mx.pb(tmp);112 mc.add(u, sink, l);113 }114 int flow = mc.max_flow(src, sink);115 116 // int ok = 1;117 // for(int i = 0; i < (int)mx.size(); i++) {118 // int id = mx[i];119 // if(mc.edges[id].c) {120 // ok = 0;121 // break;122 // }123 // }124 125 if(t != 1) puts("");126 if(ff == flow) {127 puts("YES");128 for(int i = 0; i < (int)cap.size(); i++) {129 Node x = cap[i];130 int id = x.id;131 printf("%d\n", x.c-mc.edges[id].c);132 }133 } else puts("NO");134 }135 return 0;136 }
2有源汇上下界流
对于有上下界的网络流，要求其最大或最下流，我们可以针对源汇点连一条容量无穷大的边，这样整个图就变成无源无汇的流量图了。
通常有两种方法：一，二分法，二，直接转化法
1）最大流
二分法：每次设置T到S的边的容量下界，然后判断是否存在可行流，最后是可以得到最大值的。
直接转化法：先连一条T到S的容量无穷的边，然后转化为无源无汇的可行流，做一遍网络流后判断S出边是否满流，如果不满流说明不存在可行解；否则，拆除T到S的边，然后从原图源点src, 汇点sink做网络流，最后结果就是T->S反响变的容量+src到sink的最大流
ZOJ - 3229
Shoot the Bullet
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define esp 1e-14 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pf(x) ((x)*(x)) 9 #define pb push_back 10 #define in freopen("solve_in.txt", "r", stdin); 11 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 12 #define inf 0x0f0f0f0f 13 using namespace std; 14 typedef long long LL; 15 typedef map<LL, int> MPS; 16 typedef pair<LL, LL> PII; 17 const int maxn = 1555; 18 int num[1111][400]; 19 int l[1111][400], r[1111][400]; 20 vector<int> days[400]; 21 22 struct Edge { 23 int u, v, c; 24 Edge() {} 25 Edge(int u, int v, int c):u(u), v(v), c(c) {} 26 }; 27 struct MaxFlow { 28 int n, m, src, sink; 29 vector<Edge> edges; 30 vector<int> G[maxn]; 31 int Now[maxn], Dfn[maxn]; 32 void init(int n) { 33 this->n = n; 34 for(int i = 0; i < n; i++) 35 G[i].clear(); 36 edges.clear(); 37 } 38 int add(int u, int v, int c) { 39 edges.pb(Edge(u, v, c)); 40 edges.pb(Edge(v, u, 0)); 41 m = edges.size(); 42 G[u].pb(m-2); 43 G[v].pb(m-1); 44 return m; 45 } 46 int ISAP(int s, int flow) { 47 if(s == sink) return flow; 48 int tab = n, v, now = 0, vary; 49 for(int i = 0; i < sz(G[s]); i++) { 50 Edge &e = edges[G[s][i]]; 51 if(e.c > 0) { 52 if(Dfn[s] == Dfn[v = e.v] + 1) 53 vary = ISAP(v, min(flow-now, e.c)), 54 now += vary, e.c -= vary, edges[G[s][i]^1].c += vary; 55 if(Dfn[src] == n) return now; 56 if(e.c > 0) tab = min(tab, Dfn[v]); 57 if(now == flow) break; 58 } 59 } 60 if(now == 0) { 61 if(--Now[Dfn[s]] == 0) 62 Dfn[src] = n; 63 ++Now[Dfn[s] = tab + 1]; 64 } 65 return now; 66 } 67 int getAns(int src, int sink) { 68 this->src =http://www.mamicode.com/ src; 69 this->sink = sink; 70 memset(Now, 0, sizeof Now); 71 memset(Dfn, 0, sizeof Dfn); 72 Now[0] = n; 73 int ans = 0; 74 while(Dfn[src] < n) { 75 ans += ISAP(src, inf); 76 } 77 return ans; 78 } 79 } solver ; 80 int main() { 81 82 int n, m; 83 while(scanf("%d%d", &n, &m) == 2) { 84 for(int i = 0; i < 400; i++) 85 days[i].clear(); 86 solver.init(n+m+4); 87 int src = http://www.mamicode.com/0, sink = n+m+1; 88 int S = n+m+2, T = S+1; 89 for(int i = 0; i < m; i++) { 90 int lim; 91 scanf("%d", &lim); 92 solver.add(src, i+1, inf-lim); 93 solver.add(S, i+1, lim); 94 solver.add(src, T, lim); 95 } 96 for(int i = 1; i <= n; i++) { 97 int t, c; 98 scanf("%d%d", &t, &c); 99 solver.add(i+m, sink, c);100 for(int j = 1; j <= t; j++) {101 int no, L, R;102 scanf("%d%d%d", &no, &L, &R);103 no++;104 days[i].pb(no);105 l[no][i] = L;106 r[no][i] = R;107 num[no][i] = solver.add(no, i+m, R-L)-2;108 solver.add(S, i+m, L);109 solver.add(no, T, L);110 }111 }112 int tmp = solver.add(sink, src, inf);113 solver.getAns(S, T);114 int ok = 1;115 for(int i = 0; i < sz(solver.G[S]); i++)116 if(solver.edges[solver.G[S][i]].c) {117 ok = 0;118 break;119 }120 if(!ok) {121 puts("-1\n");122 continue;123 }124 int ans = 0;125 ans += solver.edges[tmp-1].c;126 solver.edges[tmp-1].c = solver.edges[tmp-2].c = 0;127 ans += solver.getAns(src, sink);128 printf("%d\n", ans);129 for(int i = 1; i <= n; i++)130 for(int j = 0; j < sz(days[i]); j++) {131 int x = days[i][j];132 printf("%d\n", l[x][i]+solver.edges[num[x][i]^1].c);133 }134 puts("");135 }136 return 0;137 }
2）最小流
二分法：每次设置T到S的边的容量上界，然后判断是否存在可行流，同样最后是可以得到最小值的。
直接转化法：先不连T到S的边直接转化为无源无汇的可行流判断，然后连接T到S的容量无穷的边，再做一次无源无汇的网络流可行流判断，答案便是T->S反向边的容量。
以上各种方法中，每条边实际流量是容量下界+该边的反向边的容量。
ZOJ - 2567
Trade
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define esp 1e-14 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pf(x) ((x)*(x)) 9 #define pb push_back 10 #define in freopen("solve_in.txt", "r", stdin); 11 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 12 #define inf 0x0f0f0f0f 13 using namespace std; 14 typedef long long LL; 15 typedef map<LL, int> MPS; 16 typedef pair<LL, LL> PII; 17 const int maxn = 333; 18 int g[maxn][maxn]; 19 int du[maxn*2]; 20 21 struct Edge { 22 int u, v, c; 23 Edge() {} 24 Edge(int u, int v, int c):u(u), v(v), c(c) {} 25 }; 26 struct E { 27 int u, v, b, c; 28 E() {} 29 E(int u, int v, int b, int c):u(u), v(v), b(b), c(c) {} 30 }; 31 vector<E> edge; 32 33 struct MaxFlow { 34 int n, m, src, sink; 35 vector<Edge> edges; 36 vector<int> G[maxn*2]; 37 int Now[maxn*2], Dfn[maxn*2]; 38 void init(int n) { 39 this->n = n; 40 for(int i = 0; i < n; i++) 41 G[i].clear(); 42 edges.clear(); 43 } 44 int add(int u, int v, int c) { 45 edges.pb(Edge(u, v, c)); 46 edges.pb(Edge(v, u, 0)); 47 m = edges.size(); 48 G[u].pb(m-2); 49 G[v].pb(m-1); 50 return m; 51 } 52 int ISAP(int s, int flow) { 53 54 if(s == sink) return flow; 55 int v, tab = n-1, vary, now = 0; 56 for(int i = 0; i < sz(G[s]); i++) { 57 Edge &e = edges[G[s][i]]; 58 if(e.c > 0) { 59 if(Dfn[s] == Dfn[v = e.v] + 1) 60 vary = ISAP(v, min(flow-now, e.c)), 61 now += vary, e.c -= vary, edges[G[s][i]^1].c += vary; 62 if(Dfn[src] == n) return now; 63 if(e.c > 0) tab = min(tab, Dfn[v]); 64 if(now == flow) break; 65 } 66 } 67 if(now == 0) { 68 if(--Now[Dfn[s]] == 0) 69 Dfn[src] = n; 70 ++Now[Dfn[s] = tab + 1]; 71 } 72 return now; 73 } 74 int getAns(int src, int sink) { 75 76 this->src =http://www.mamicode.com/ src; 77 this->sink = sink; 78 memset(Dfn, 0, sizeof Dfn); 79 memset(Now, 0, sizeof Now); 80 Now[0] = n; 81 int ans = 0; 82 while(Dfn[src] < n) 83 ans += ISAP(src, inf); 84 return ans; 85 } 86 87 } solver; 88 89 90 int main() { 91 92 int n, m, p; 93 while(scanf("%d%d%d", &n, &m, &p) == 3) { 94 int src = http://www.mamicode.com/0, sink = n+m+1; 95 memset(du, 0, sizeof du); 96 int S = n+m+2, T = S+1; 97 edge.clear(); 98 solver.init(n+m+4); 99 for(int i = 1; i <= p; i++) {100 int u, v;101 scanf("%d%d", &u, &v);102 edge.pb(E(u, v+n, 0, 1));103 }104 for(int i = 0; i < n; i++)105 edge.pb(E(src, i+1, 2, inf));106 for(int j = 0; j < m; j++)107 edge.pb(E(j+1+n, sink, 2, inf));108 for(int i = 0; i < sz(edge); i++) {109 E e = edge[i];110 du[e.u] -= e.b;111 du[e.v] += e.b;112 solver.add(e.u, e.v, e.c-e.b);113 }114 for(int i = 0; i < S; i++) {115 if(du[i] > 0)116 solver.add(S, i, du[i]);117 else if(du[i] < 0)118 solver.add(i, T, -du[i]);119 }120 solver.getAns(S, T);121 solver.add(sink, src, inf);122 solver.getAns(S, T);123 int ok = 1;124 for(int i = 0; i < sz(solver.G[S]); i++) {125 Edge e = solver.edges[solver.G[S][i]];126 if(e.c) {127 ok = 0;128 break;129 }130 }131 if(!ok) puts("-1");132 else {133 vector<int> ans;134 for(int i = 0; i < p; i++) {135 if(solver.edges[i<<1|1].c)136 ans.pb(i+1);137 }138 cout << sz(ans) << endl;139 for(int i = 0; i < sz(ans); i++)140 printf("%d%c", ans[i], i == sz(ans)-1 ? ‘\n‘ : ‘ ‘);141 }142 }143 return 0;144 }
上下界网络流小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。