SGU 176 Flow construction 有源汇 有上下界的最小流
题意就是给出一个图。有源汇
然后每条边都有容量的上下界限制。
问的是是否有一个最小流，使得每条边得流量都满足流量限制，并且流量守恒
我使用的是二分的方法。
每次二分都要重新构图，然后计算。
构图的方法是按照论文中所说。
设原来的源汇为s, t， 附加源汇为S, T
对于一个点i，计算流入该点的下界总和减去流出该点的下界总和为M[i].
如果M[i]是正数，添加边(S,i)，容量为M[i]
否则添加边(i, T) 容量为-M[i]
然后对于每条边，设上下届分为up和down， 起点终点为u,v
那么添加边(u, v)流量为up - down即可
由于我们要二分一个流量然后判断可行。
假设二分的流量是x,则添加边(t, s) 流量为x
然后求最大流看是否使得源s连出去的边都满流。若都满流即为可行流。
最后求得的最小的该x即为最终原图中的最小流
输出边时则输出边得流量加上原来的down。因为我们之前减掉了。
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <cstdlib>#include <cmath>#include <map>#include <sstream>#include <queue>#include <vector>#define MAXN 111#define MAXM 21111#define eps 1e-8#define INF 1000000009using namespace std;struct EDGE{ int v, next; int w;} edge[MAXM];int head[MAXN], e;inline void init(){ memset(head, -1, sizeof(head)); e = 0;}inline void add(int u, int v, int w){ edge[e].v = v; edge[e].w = w; edge[e].next = head[u]; head[u] = e++; edge[e].v = u; edge[e].w = 0; edge[e].next = head[v]; head[v] = e++;}int n;int h[MAXN];int gap[MAXN];int src, des;inline int dfs(int pos, int cost){ if (pos == des) return cost; int j, minh = n - 1; int lv = cost, d; for (j = head[pos]; j != -1; j = edge[j].next) { int v = edge[j].v; int w = edge[j].w; if(w > 0) { if (h[v] + 1 == h[pos]) { if (lv < edge[j].w) d = lv; else d = edge[j].w; d = dfs(v, d); edge[j].w -= d; edge[j ^ 1].w += d; lv -= d; if (h[src] >= n) return cost - lv; if (lv == 0) break; } if (h[v] < minh) minh = h[v]; } } if (lv == cost) { --gap[h[pos]]; if (gap[h[pos]] == 0) h[src] = n; h[pos] = minh + 1; ++gap[h[pos]]; } return cost - lv;}int sap(){ int ret = 0; memset(gap, 0, sizeof(gap)); memset(h, 0, sizeof(h)); gap[0] = n; while (h[src] < n) ret += dfs(src, INF); return ret;}int nt, m;int xj[MAXN];int uu[MAXM], vv[MAXM], low[MAXM], z[MAXM];int id[MAXN][MAXN], eid, total, limit;void build(int x){ init(); for(int i = 0; i < m; i++) { id[uu[i]][vv[i]] = e; add(uu[i], vv[i], z[i] - low[i]); } for(int i = 1; i <= nt; i++) { if(xj[i] > 0) add(src, i, xj[i]); else add(i, des, -xj[i]); } add(nt, 1, x);}void gao(){ int l = 0, r = limit, mid; while(l <= r) { mid = (l + r) >> 1; build(mid); if(sap() == total) r = mid - 1; else l = mid + 1; } build(l); sap(); printf("%d\n", l); for(int i = 0; i < m; i++) { int tmp = id[uu[i]][vv[i]]; printf("%d ", edge[tmp ^ 1].w + low[i]); } printf("\n");}int main(){ while(scanf("%d%d", &nt, &m) != EOF) { init(); total = 0; limit = 0; memset(xj, 0, sizeof(xj)); for(int i = 0; i < m; i++) { scanf("%d%d%d%d", &uu[i], &vv[i], &z[i], &low[i]); if(low[i] == 1) low[i] = z[i]; xj[vv[i]] += low[i]; xj[uu[i]] -= low[i]; if(uu[i] == 1) limit += z[i]; } src = nt + 1; des = nt + 2; n = des; for(int i = 1; i <= nt; i++) if(xj[i] > 0) total += xj[i]; build(INF); if(sap() != total) printf("Impossible\n"); else gao(); } return 0;}