此类问题可以分为三小类问题:
一、无源汇有上下界最大流
二、有源汇有上下界最大流
三、有源汇有上下界最小流
关于这个可以参考周源的《一种简易的方法求解流量有上下界的网络中的网络流问题》
1、无源汇有上下界最大流(可行流)
题目链接: sgu194 Reactor Cooling
#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <iostream> #include <algorithm> using namespace std; const int MAXV = 222; const int MAXE = 2*MAXV*MAXV; const int INF = 0x3f3f3f3f; struct Edge { int u, v, cap, next; Edge() {} Edge(int t_u, int t_v, int t_cap, int t_next)\ : u(t_u), v(t_v), cap(t_cap), next(t_next) {} }; Edge edges[MAXE]; //int init_cap[MAXE]; int n, m, source, sink, edge_sum, max_flow; int head[MAXV], dis[MAXV]; int low[MAXE], in[MAXV], out[MAXV]; void Init() { edge_sum = 0; memset(head, -1, sizeof(head)); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); } void addEdge(int u, int v, int cap) { edges[edge_sum].u = u; edges[edge_sum].v = v; edges[edge_sum].cap = cap; edges[edge_sum].next = head[u]; head[u] = edge_sum++; edges[edge_sum].u = v; edges[edge_sum].v = u; edges[edge_sum].cap = 0; edges[edge_sum].next = head[v]; head[v] = edge_sum++; } int bfs() { int i, v, tmp; queue<int> q; memset(dis, 0, sizeof(dis)); dis[source] = 1; q.push(source); while(!q.empty()) { v = q.front(); q.pop(); for(i = head[v]; i != -1; i = edges[i].next) { tmp = edges[i].v; if(!dis[tmp] && edges[i].cap) { dis[tmp] = dis[v] + 1; if(tmp == sink) return 1; q.push(tmp); } } } return 0; } int dfs(int cur, int cp) { if(cur == sink) return cp; int tmp = 0, i, a, t; for(i = head[cur]; i != -1 && tmp < cp; i = edges[i].next) { a = edges[i].v; if(dis[a] == dis[cur]+1 && edges[i].cap) { t = dfs(a, min(edges[i].cap, cp-tmp)); edges[i].cap -= t; edges[i^1].cap += t; tmp += t; } } if(!tmp) dis[cur] = -1; return tmp; } void dinic() { max_flow = 0; while(bfs()) max_flow += dfs(source, INF); return ; } int main() { //freopen("aa.in", "r", stdin); //freopen("bb.out", "w", stdout); int u, v, l, h, tm; while(scanf("%d %d", &n, &m) != EOF) { Init(); tm = m; while(m--) { scanf("%d %d %d %d", &u, &v, &l, &h); //init_cap[edge_sum] = h - l; low[edge_sum] = l; addEdge(u, v, h - l); in[v] += l; out[u] += l; //low[edge_sum-2] = l; } source = 0, sink = n + 1; for(int i = 1; i <= n; ++i) { if(in[i] > out[i]) addEdge(source, i, in[i]-out[i]); if(in[i] < out[i]) addEdge(i, sink, out[i] - in[i]); } n += 2; bool flag = true; dinic(); for(int i = head[source]; i != -1; i = edges[i].next) { if(edges[i].cap > 0) { flag = false; break; } } if(!flag) printf("NO\n"); else { printf("YES\n"); for(int i = 0; i < 2*tm; i += 2) { printf("%d\n", low[i] + edges[i^1].cap); //printf("%d\n", low[i] + init_cap[i]-edges[i].cap); } } } return 0; }
2、有源汇有上下界最大流
#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <iostream> #include <algorithm> using namespace std; const int MAXV = 1500; const int MAXE = 1000010; const int INF = 0x3f3f3f3f; struct Edge { int u, v, cap, next; Edge() {} Edge(int t_u, int t_v, int t_cap, int t_next)\ : u(t_u), v(t_v), cap(t_cap), next(t_next) {} }; Edge edges[MAXE]; int n, m, source, sink, edge_sum, max_flow; int head[MAXV], dis[MAXV]; int du[MAXV]; int low[400][1010], pos[400][1010]; void Init() { edge_sum = 0; memset(head, -1, sizeof(head)); memset(du, 0, sizeof(du)); memset(low, -1, sizeof(low)); //memset(in, 0, sizeof(in)); //memset(out, 0, sizeof(out)); } void addEdge(int u, int v, int cap) { edges[edge_sum].u = u; edges[edge_sum].v = v; edges[edge_sum].cap = cap; edges[edge_sum].next = head[u]; head[u] = edge_sum++; edges[edge_sum].u = v; edges[edge_sum].v = u; edges[edge_sum].cap = 0; edges[edge_sum].next = head[v]; head[v] = edge_sum++; } int bfs() { int i, v, tmp; queue<int> q; memset(dis, 0, sizeof(dis)); dis[source] = 1; q.push(source); while(!q.empty()) { v = q.front(); q.pop(); for(i = head[v]; i != -1; i = edges[i].next) { tmp = edges[i].v; if(!dis[tmp] && edges[i].cap) { dis[tmp] = dis[v] + 1; if(tmp == sink) return 1; q.push(tmp); } } } return 0; } int dfs(int cur, int cp) { if(cur == sink) return cp; int tmp = 0, i, a, t; for(i = head[cur]; i != -1 && tmp < cp; i = edges[i].next) { a = edges[i].v; if(dis[a] == dis[cur]+1 && edges[i].cap) { t = dfs(a, min(edges[i].cap, cp-tmp)); edges[i].cap -= t; edges[i^1].cap += t; tmp += t; } } if(!tmp) dis[cur] = -1; return tmp; } void dinic() { max_flow = 0; while(bfs()) max_flow += dfs(source, INF); return ; } int main() { //freopen("aa.in", "r", stdin); //freopen("bb.out", "w", stdout); int t_n, G, C, D, T, L, R; while(scanf("%d %d", &n, &m) != EOF) { Init(); for(int i = 1; i <= m; ++i) { scanf("%d", &G); addEdge(n + i, n + m + 1, INF - G); du[n+i] -= G; du[n+m+1] += G; //out[n+i] += G; //in[n+m+1] += G; } for(int i = 1; i <= n; ++i) { scanf("%d %d", &C, &D); addEdge(0, i, D); for(int j = 1; j <= C; ++j) { scanf("%d %d %d", &T, &L, &R); T++; pos[i][T] = edge_sum; addEdge(i, n + T, R - L); du[i] -= L; du[n+T] += L; //out[i] += L; //in[n+T] += L; low[i][T] = L; } } addEdge(n + m + 1, 0, INF); source = n + m + 2, sink = n + m + 3; for(int i = 0; i <= n + m + 1; ++i) { if(du[i] > 0) addEdge(source, i, du[i]); if(du[i] < 0) addEdge(i, sink, -du[i]); //if(in[i] > out[i]) //addEdge(source, i, in[i] - out[i]); //if(in[i] < out[i]) //addEdge(i, sink, out[i] - in[i]); } bool flag = true; t_n = n; n = n + m + 4; dinic(); for(int i = head[source]; i != -1; i = edges[i].next) { if(edges[i].cap > 0) { flag = false; break; } } if(!flag) { printf("-1\n"); } else { n -= 2; //head[source] = -1, head[sink] = -1; source = 0, sink = t_n + m + 1; // dinic(); printf("%d\n", max_flow); for(int i = 1; i <= t_n; ++i) { for(int j = 1; j <= m; ++j) { if(low[i][j] != -1) printf("%d\n", low[i][j] + edges[pos[i][j]^1].cap); } } } printf("\n"); } return 0; }
3、有源汇有上下界最小流
题目链接: sgu176 Flow
construction
#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <iostream> #include <algorithm> using namespace std; const int MAXV = 150; const int MAXE = 2*MAXV*MAXV; const int INF = 0x3f3f3f3f; struct Edge { int u, v, cap, next; Edge() {} Edge(int t_u, int t_v, int t_cap, int t_next)\ : u(t_u), v(t_v), cap(t_cap), next(t_next) {} }; Edge edges[MAXE]; int n, m, source, sink, edge_sum, max_flow, t_flow; int head[MAXV], dis[MAXV]; int in[MAXV], out[MAXV]; int low[MAXE], save[MAXE]; void Init() { edge_sum = 0; t_flow = 0; memset(head, -1, sizeof(head)); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); memset(low, 0, sizeof(low)); } void addEdge(int u, int v, int cap) { edges[edge_sum].u = u; edges[edge_sum].v = v; edges[edge_sum].cap = cap; edges[edge_sum].next = head[u]; head[u] = edge_sum++; edges[edge_sum].u = v; edges[edge_sum].v = u; edges[edge_sum].cap = 0; edges[edge_sum].next = head[v]; head[v] = edge_sum++; } int bfs() { int i, v, tmp; queue<int> q; memset(dis, 0, sizeof(dis)); dis[source] = 1; q.push(source); while(!q.empty()) { v = q.front(); q.pop(); for(i = head[v]; i != -1; i = edges[i].next) { tmp = edges[i].v; if(!dis[tmp] && edges[i].cap) { dis[tmp] = dis[v] + 1; if(tmp == sink) return 1; q.push(tmp); } } } return 0; } int dfs(int cur, int cp) { if(cur == sink) return cp; int tmp = 0, i, a, t; for(i = head[cur]; i != -1 && tmp < cp; i = edges[i].next) { a = edges[i].v; if(dis[a] == dis[cur]+1 && edges[i].cap) { t = dfs(a, min(edges[i].cap, cp-tmp)); edges[i].cap -= t; edges[i^1].cap += t; tmp += t; } } if(!tmp) dis[cur] = -1; return tmp; } void dinic() { max_flow = 0; while(bfs()) max_flow += dfs(source, INF); return ; } int Binary_search(int l, int r) { int mid, ans = -1; while(l <= r) { mid = (l + r) / 2; edges[head[n-2]].cap = mid; edges[head[n-2]^1].cap = 0; dinic(); if(max_flow == t_flow) { //cout << max_flow << " " << t_flow << endl; r = mid - 1; ans = mid; } else l = mid + 1; for(int i = 0; i < edge_sum; ++i) { edges[i].cap = save[i]; } } if(ans != -1) { edges[head[n-2]].cap = ans; edges[head[n-2]^1].cap = 0; dinic(); } return ans; } int main() { //freopen("aa.in", "r", stdin); //freopen("bb.out", "w", stdout); int u, v, z, c; while(scanf("%d %d", &n, &m) != EOF) { Init(); for(int i = 1; i <= m; ++i) { scanf("%d %d %d %d", &u, &v, &z, &c); if(c == 0) { addEdge(u, v, z); } else if(c == 1) { t_flow += z; //// low[edge_sum] = z; in[v] += z; out[u] += z; addEdge(u, v, 0); } } source = 0, sink = n + 1; for(int i = 1; i <= n; ++i) { addEdge(source, i, in[i]); addEdge(i, sink, out[i]); } addEdge(n, 1, INF); n += 2; //////////////// for(int i = 0; i < edge_sum; ++i) { save[i] = edges[i].cap; } int l = 0, r = INF; int ans = Binary_search(l, r); if(ans == -1) { printf("Impossible\n"); } else { printf("%d\n", ans); for(int i = 0; i < 2*m; i += 2) { if(i == 0) printf("%d", low[i]+edges[i^1].cap); else printf(" %d", low[i]+edges[i^1].cap); } printf("\n"); } } return 0; }
#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <iostream> #include <algorithm> using namespace std; const int MAXV = 150; const int MAXE = 2*MAXV*MAXV; const int INF = 0x3f3f3f3f; struct Edge { int u, v, cap, next; Edge() {} Edge(int t_u, int t_v, int t_cap, int t_next)\ : u(t_u), v(t_v), cap(t_cap), next(t_next) {} }; Edge edges[MAXE]; int n, m, source, sink, edge_sum, max_flow, t_flow; int head[MAXV], dis[MAXV]; int in[MAXV], out[MAXV]; int low[MAXE]; void Init() { edge_sum = 0; t_flow = 0; memset(head, -1, sizeof(head)); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); memset(low, 0, sizeof(low)); } void addEdge(int u, int v, int cap) { edges[edge_sum].u = u; edges[edge_sum].v = v; edges[edge_sum].cap = cap; edges[edge_sum].next = head[u]; head[u] = edge_sum++; edges[edge_sum].u = v; edges[edge_sum].v = u; edges[edge_sum].cap = 0; edges[edge_sum].next = head[v]; head[v] = edge_sum++; } int bfs() { int i, v, tmp; queue<int> q; memset(dis, 0, sizeof(dis)); dis[source] = 1; q.push(source); while(!q.empty()) { v = q.front(); q.pop(); for(i = head[v]; i != -1; i = edges[i].next) { tmp = edges[i].v; if(!dis[tmp] && edges[i].cap) { dis[tmp] = dis[v] + 1; if(tmp == sink) return 1; q.push(tmp); } } } return 0; } int dfs(int cur, int cp) { if(cur == sink) return cp; int tmp = 0, i, a, t; for(i = head[cur]; i != -1 && tmp < cp; i = edges[i].next) { a = edges[i].v; if(dis[a] == dis[cur]+1 && edges[i].cap) { t = dfs(a, min(edges[i].cap, cp-tmp)); edges[i].cap -= t; edges[i^1].cap += t; tmp += t; } } if(!tmp) dis[cur] = -1; return tmp; } void dinic() { max_flow = 0; while(bfs()) max_flow += dfs(source, INF); return ; } int main() { //freopen("aa.in", "r", stdin); //freopen("bb.out", "w", stdout); int u, v, z, c; int ans; while(scanf("%d %d", &n, &m) != EOF) { Init(); for(int i = 1; i <= m; ++i) { scanf("%d %d %d %d", &u, &v, &z, &c); if(c == 0) { addEdge(u, v, z); } else if(c == 1) { t_flow += z; low[edge_sum] = z; out[u] += z; in[v] += z; addEdge(u, v, 0); } } source = 0, sink = n + 1; for(int i = 1; i <= n; ++i) { addEdge(source, i, in[i]); addEdge(i, sink, out[i]); } addEdge(n, 1, INF); n += 2; dinic(); ans = edges[head[n-2]^1].cap; if(max_flow != t_flow) { printf("Impossible\n"); } else { edges[head[n-2]].cap = 0; edges[head[n-2]^1].cap = 0; n -= 2; source = n, sink = 1; dinic(); ans -= max_flow; if(ans < 0) { edges[head[n]].cap = 0; edges[head[n]^1].cap = 0; addEdge(0, 1, -ans); //edges[edge_sum].u = 0; //edges[edge_sum].v = 1; //edges[edge_sum].cap = -ans; //edges[edge_sum].next = head[0]; //head[0] = edge_sum++; source = 0, sink = n; n++; dinic(); ans = 0; } printf("%d\n", ans); bool first = true; for(int i = 0; i < 2*m; i += 2) { if(first) { first = false; printf("%d", low[i]+edges[i^1].cap); } else printf(" %d", low[i]+edges[i^1].cap); } printf("\n"); } } return 0; }