题意就是给出一个图。有源汇
然后每条边都有容量的上下界限制。
问的是是否有一个最小流，使得每条边得流量都满足流量限制，并且流量守恒
我使用的是二分的方法。
每次二分都要重新构图，然后计算。
构图的方法是按照论文中所说。
设原来的源汇为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 1000000009
using 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;
}