题解：P6931 [ICPC 2017 WF] Mission Improbable

· · 题解

思路：

可以简化一下问题，假设 Patrick 把箱子都拿走但是原来有箱子的位置留下一个，现在要放箱子使得每行每列最大值都满足，最少放多少个。

设第 i 行的最大值是 H(i)，第列的是 W(i)。没有箱子的行可以不用去管，假设每行每列都有一个地方放 \frac{H(i)}{W(i)}，现在如果有一个 H(i)=W(j)，而且原来 (i,j) 位置上有箱子，那么就可以在 (i,j) 位置上放 H(i) 个箱子同时满足第 i 行与第 j 列，获得 H(i)-1 的收益。

按照以上思路，这题就做完了，统一答案随便搞一下即可。

代码：

#include<bits/stdc++.h>
#define il inline
#define vd void
using namespace std;
typedef long long ll;
il int gi() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (isdigit(ch))x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
ll A[101][101], H[101], W[101];
int S, T, fir[210], dis[30010], nxt[30010], w[30010], id = 1;
ll cost[30010];
il vd link(int a, int b, ll d) {
    nxt[++id] = fir[a], fir[a] = id, dis[id] = b, w[id] = 1, cost[id] = d;
    nxt[++id] = fir[b], fir[b] = id, dis[id] = a, w[id] = 0, cost[id] = -d;
}
il bool Mincost(ll&total) {
    static ll dist[210];
    static int que[210], hd, tl, lst[210];
    static bool inq[210];
    memset(dist, 63, sizeof dist);
    dist[S] = 0;
    hd = tl = 0;
    que[tl++] = S;
    inq[S] = 1;
    lst[T] = 0;
    while (hd ^ tl) {
        int x = que[hd];
        for (int i = fir[x]; i; i = nxt[i])
            if (w[i] && dist[dis[i]] > dist[x] + cost[i]) {
                dist[dis[i]] = dist[x] + cost[i], lst[dis[i]] = i;
                if (!inq[dis[i]])inq[dis[i]] = 1, que[tl++] = dis[i], tl %= 210;
            }
        inq[x] = 0, ++hd, hd %= 210;
    }
    for (int i = lst[T]; i; i = lst[dis[i ^ 1]])w[i] = 0, w[i ^ 1] = 1, total -= cost[i];
    return lst[T];
}
int main() {
    int n = gi(), m = gi();
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            A[i][j] = gi();
            if (A[i][j])ans += A[i][j] - 1;
            H[i] = std::max(H[i], A[i][j]);
            W[j] = std::max(W[j], A[i][j]);
        }
    for (int i = 1; i <= n; ++i)if (H[i])ans -= H[i] - 1;
    for (int i = 1; i <= m; ++i)if (W[i])ans -= W[i] - 1;
    S = 0, T = n + m + 1;
    for (int i = 1; i <= n; ++i)link(S, i, 0);
    for (int i = 1; i <= m; ++i)link(i + n, T, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (A[i][j] && H[i] == W[j] && H[i])link(i, n + j, -H[i] + 1);
    while (Mincost(ans));
    printf("%lld\n", ans);
    return 0;
}

完结撒花，谢谢Thanks♪(･ω･)ﾉ