· 博主智商拙计
· 代码各种丑
· 真· 原 (piao) 创 (qie)
连考了二次上下界网络流……
还好第一次考完后马上就恶补了> <~
不过今天又有点晕 (kun) , 于是写下来以防又悲剧......
推荐：
1、《一种简易的方法求解流量有上下界的网络中网络流问题》( 周源 )
2、http://wenku.baidu.com/view/042856687e21af45b307a875.html
建模什么的就不啰嗦了……反正要满足流量平衡.
考虑没有下界的限制, 那么每条边的容量应当是 max(u, v) - min(u, v), 这些边构成图 G '
然后我们设图 G ' 中的一条可行流 f, 其在边 e(u, v) 的流量为 g(u, v)
显然如果想把这条可行流映射到原图中, 必然要满足以下的流量平衡条件 ：
∑(min(v, i) + g(v, i)) = ∑ (min(i, u) + g(i, u))
将上式变形, 可得到：
∑(min(v, i) - min(i, u)) = ∑ (g(i, u) - g(v, i))
回到图 G ' , 假设图 G ‘ 的流没有满足流量平衡……也就是说∑ (g(i, u) - g(v, i)) ≠ 0, 那么很明显的是, 我们可以虚拟一个源或者汇, 流入其不足的流量, 或者流出其多余的流量.
而流入的流量 / 流出的流量的大小正好为 ∑ (g(i, u) - g(v, i)) = ∑(min(v, i) - min(i, u))
于是……新建一个源 _S, 一个汇 _T, 按照上述方法连边. 然后跑 _S -> _T 的最大流, 如果 _S 的所有出边以及 _T 的所有入边都满流, 那么表示流量平衡条件满足.
具体的构造方法是 :
1、先把原图变成无源无汇, 也就是T -> S 连一条容量为 ∞ 的边 ( 不然加入新源汇的话就有多个源、汇了……)
2、建立边 e (u, v), 容量c (u, v) = max(u, v) - min(u, v)
3、点 i 的 ∑(min(v, i) - min(i, u)) > 0 则连一条边e ( _S, i) , 容量 c ( _S, i) = ∑(min(v, i) - min(i, u))
反之连一条边 e ( i, _T )
然后跑 _S -> _T 最大流即可. 跑出来的最大流满足原图的流量平衡条件, 也就是说是原图的一条可行流.
拓展：
求原图最大流：跑完 _S -> _T 后, 再跑 S -> T 即可. ( 很不理解为什么论文都说要二分……明明求出可行流了直接继续增广就可以了嘛 )
最小费用最大流 ：同上. 带费用而已.
参考：CSDN Delayyy [例题] 最小矩阵差 - 有上下界的网络流问题
http://blog.csdn.net/delayyy/article/details/8660158
代码的话呢……
那就放 Delayyy君的例题吧……
写得好丑> <
而且一直忘记加 e (T, S) 了……
#include <cstdio>
#include <cstdlib>
#include <algorithm>
const int INF = ~0U>>1;
using namespace std;
int a[210][210];
int c[100010], edv[100010], next[100010];
int g[1010], dima[1010], t[1010];
int tot[1010], p[210][210];
int n, m, min_p, max_p, min_r, S, T, sg, set, _S, _T;
void add(int x, int y, int t)
{
c[++sg] = y, next[sg] = g[x], g[x] = sg, edv[sg] = t;
c[++sg] = x, next[sg] = g[y], g[y] = sg, edv[sg] = 0;
}
bool BFS(int sta, int ent)
{
int head = 1, tail = 1, p[1010]; p[1] = sta; dima[sta] = 0; t[sta] = ++set;
for (; head <= tail; ++head)
for (int x = g[p[head]]; x; x = next[x])
if (t[c[x]] != set && edv[x ^ 1])
{
p[++tail] = c[x]; dima[c[x]] = dima[p[head]] + 1; t[c[x]] = set;
if (c[x] == ent) return true;
}
return false;
}
int DFS(int z, int push, int ent)
{
if (z == ent || !push) return push;
int f, flow = 0;
for (int x = g[z]; x; x = next[x])
if (edv[x] && t[c[x]] == set)
if (dima[z] == dima[c[x]] + 1 && (f = DFS(c[x], push > edv[x] ? edv[x] : push, ent)))
{
flow += f; push -= f;
edv[x] -= f; edv[x ^ 1] += f;
if (!push) return flow;
}
dima[z] = INF;
return flow;
}
bool compare(int j)
{
int tot_S = 0, tot_T = 0, ans = 0, x = 0, y = 0;
sg = 1;
for (int i = 0; i <= n + m + 3; ++i) g[i] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
add(i, j + n, max_p - min_p);
for (int i = 1; i <= n; ++i)
{
int sep = tot[i] > j ? tot[i] - j : 0; x += sep;
add(S, i, tot[i] + j - sep);
if ((sep -= m * min_p) > 0)
add(_S, i, sep), tot_S += sep;
else if (sep < 0)
add(i, _T, -sep), tot_T -= sep;
}
for (int i = n + m; i > n; --i)
{
int sep = tot[i] > j ? tot[i] - j : 0; y += sep;
add(i, T, tot[i] + j - sep);
if ((sep -= n * min_p) > 0)
add(i, _T, sep), tot_T += sep;
else if (sep < 0)
add(_S, i, -sep), tot_S -= sep;
}
add(S, _T, x); tot_T += x; add(_S, T, y); tot_S += y; add(T, S, INF);
while (BFS(_T, _S)) ans += DFS(_S, INF, _T);
if (ans != tot_S) return false;
return true;
}
int main()
{
freopen("mat.in", "r", stdin);
freopen("mat.out", "w", stdout);
scanf("%d %d", &n, &m); _S = n + m + 2, _T = n + m + 3; S = 0; T = n + m + 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &min_p), min_r += min_p,
tot[j + n] += min_p, tot[i] += min_p;
scanf("%d %d", &min_p, &max_p);
int l = 0, r = min_r, j, ans;
for (; j = (l + r) >> 1, l <= r; )
if (compare(j)) ans = j, r = j - 1;
else l = j + 1;
compare(ans); printf("%d", ans);
for (int i = 1; i <= n; ++i)
for (int x = g[i]; x; x = next[x])
if (c[x] > n && c[x] <= n + m)
p[i][c[x] - n] = edv[x ^ 1];
for (int i = 1; printf("\n"), i <= n; ++i)
for (int j = 1; j <= m; ++j)
printf("%d ", p[i][j] + min_p);
}