题解：UVA11082 矩阵解压 Matrix Decompressing

· · 题解

思路分析

因该是还有什么神奇的解法，不然 20 的数值上限确实不算大。

考虑使用网络流求解。当我们将 A_{i,j} 设为 v 的时候，可以理解为从 RowSum(i)=\sum_{j=1}^mA_{i,j} 中分配了 v 到 ColumnSum(j)=\sum_{i=1}^nA_{i,j} 中。

也就是说我们实际上就是将每一行的“流量”分配到每一列上。显然有解的前提下这些流量会全部从行流向列。

所以我们从原点向行建边，上限就是这一行的和，随后从列向汇点建边，下限就是这一列的和。有解的情况下，网络流一定能给我们构造出来一组解。

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node { int p, v, nt; }e[40005]; int h[2005], cne;
inline void ins(int l, int r, int v) {
    e[++cne].nt = h[l]; e[cne].p = r; e[cne].v = v; h[l] = cne;
    e[++cne].nt = h[r]; e[cne].p = l; e[cne].v = 0; h[r] = cne;
}
int qp, n, m, k, s, t, d[2005], tp, th[2005], ans[25][25]; queue<int>q;
inline bool bfs() {
    memset(d, 0, sizeof d);
    d[s] = 1; q.emplace(s);
    while (q.size()) {
        tp = q.front(); q.pop();
        for (int i = h[tp], sp; i; i = e[i].nt)
            if (!d[sp = e[i].p] && e[i].v)
                d[sp] = d[tp] + 1, q.emplace(sp);
    }
    return d[t];
}
inline int dfs(int p, int fs) {
    if (p == t || !fs) return fs; int ret = 0;
    for (int& i = th[p], sp, v; i; i = e[i].nt)
        if (d[sp = e[i].p] == d[p] + 1 && (v = dfs(sp, min(fs - ret, e[i].v)))) {
            ret += v; e[i].v -= v; e[i ^ 1].v += v;
            if (ret == fs) return ret;
        }
    return ret;
}
signed main() {
    ios::sync_with_stdio(0); cin >> qp;
    for (int c = 1; c <= qp; ++c) {
        memset(h, 0, sizeof h); cne = 1;
        cin >> n >> m; s = n + m + 1, t = s + 1;
        for (int i = 1, a = 0, b; i <= n; ++i)
            cin >> b, b -= a, a += b, ins(s, i, b - m);
        for (int i = 1, a = 0, b; i <= m; ++i)
            cin >> b, b -= a, a += b, ins(i + n, t, b - n);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                ins(i, j + n, 19);
        while (bfs())
            memcpy(th, h, sizeof h),
            dfs(s, 1e8);
        cout << "Matrix " << c << endl;
        for (int i = 1; i <= n; i++)
            for (int j = h[i]; j; j = e[j].nt)
                if (e[j].p > n && e[j].p <= n + m)
                    ans[i][e[j].p - n] = e[j].v;
        for (int i = 1; i <= n; ++i, cout << endl)
            for (int j = 1; j <= m; ++j)
                cout << 20 - ans[i][j] << " ";
    }
}