\(\mathcal{Description}\)

Link.

在一个 \(n\times n\) 的方格图中，有一些格子已经放了零件，有一些格子可以放零件，其余格子不能放零件。求至多放多少个零件，满足第 \(i\) 行与第 \(i\) 列中零件个数相等；任意一行或一列的零件数量不超过总数量的 \(\frac{A}{B}\)。\(n\le40\)。

\(\mathcal{Solution}\)

能猜测是行列连边的二分图网络模型，但注意到网络流很难处理 \(\frac{A}{B}\) 这个比较“全局性”的限制，这提示我们可以直接枚举行列个数上限 \(x\)，若能求出在此上限下最多放置的零件个数就能判断是否合法了。

进一步，对于每个方格“放不放零件”这一问题，在网络中必须保证只有两种状态。即，每个方格都明确“放”还是“不放”。黑白染色的最小割在这里不使用，我们转而考虑用“流最大”来限制每个方格都明确选择，用网络流的另一个维度——费用，来得到答案最大。

我已经尽力描述这题的 motivation 了 qwq，接下来直接给出建图模型：

\(S\) 连向行点 \(r_i\)，流量为第 \(i\) 行已放和能放的零件数量，费用为 \(0\)；
\(r_i\) 连向列点 \(c_i\)，流量为枚举的 \(x\)，费用为 \(0\)；
\(c_i\) 连向 \(T\)，流量为第 \(i\) 列已放和能放的零件数量，费用为 \(0\)；
对于能放但未放的格子 \((i,j)\)，连接 \(r_i,c_j\)，流量为 \(1\)，费用为 \(1\)。

注意把“放的最大”转为“不放的最小”，再用最小费用流。

\(\mathcal{Code}\)

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)

#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

typedef std::pair<int, int> PII;

#define fi first

#define se second

inline int imax(const int u, const int v) { return u < v ? v : u; }

inline int imin(const int u, const int v) { return u < v ? u : v; }

const int MAXN = 40, IINF = 0x3f3f3f3f;

int n, A, B, row[MAXN + 5], col[MAXN + 5];

char str[MAXN + 5][MAXN + 5];

namespace CFG { // cost flow graph.

const int MAXND = MAXN * 2 + 2, MAXEG = MAXN * (MAXN + 3);

int S, T, ecnt = 1, head[MAXND + 5], curh[MAXND + 5];

int dis[MAXND + 5], hig[MAXND + 5];

bool instk[MAXND + 5];

struct Edge { int to, flw, cst, nxt; } graph[MAXEG * 2 + 5];

inline void clear() {

    ecnt = 1;

    rep (i, S, T) head[i] = hig[i] = dis[i] = instk[i] = 0;

}

inline void link(const int s, const int t, const int f, const int c) {

    // printf("%d %d %d %d\n", s, t, f, c);

    graph[++ecnt] = { t, f, c, head[s] }, head[s] = ecnt;

    graph[++ecnt] = { s, 0, -c, head[t] }, head[t] = ecnt;

}

inline bool dijkstra() {

    static std::priority_queue<PII, std::vector<PII>, std::greater<PII> > heap;

    rep (i, S, T) hig[i] += dis[i], dis[i] = IINF;

    heap.push({ dis[S] = 0, S });

    while (!heap.empty()) {

        PII p(heap.top()); heap.pop();

        if (dis[p.se] != p.fi) continue;

        for (int i = head[p.se], v; i; i = graph[i].nxt) {

            int d = p.fi + graph[i].cst + hig[p.se] - hig[v = graph[i].to];

            assert(!graph[i].flw || graph[i].cst + hig[p.se] - hig[v] >= 0);

            if (graph[i].flw && dis[v] > d) heap.push({ dis[v] = d, v });

        }

    }

    return dis[T] != IINF;

}

inline PII augment(const int u, int iflw) {

    if (u == T) return { iflw, 0 };

    PII ret(0, 0); instk[u] = true;

    for (int &i = curh[u], v; i; i = graph[i].nxt) {

        if (graph[i].flw && !instk[v = graph[i].to]

          && dis[v] == dis[u] + hig[u] - hig[v] + graph[i].cst) {

            PII tmp(augment(v, imin(iflw, graph[i].flw)));

            ret.fi += tmp.fi, ret.se += graph[i].cst * tmp.fi + tmp.se;

            iflw -= tmp.fi, graph[i].flw -= tmp.fi, graph[i ^ 1].flw += tmp.fi;

            if (!iflw) break;

        }

    }

    if (ret.fi) instk[u] = false;

    return ret;

}

inline PII dinic() {

    PII ret(0, 0);

    while (dijkstra()) {

        rep (i, S, T) curh[i] = head[i], instk[i] = false;

        PII tmp(augment(S, IINF));

        ret.fi += tmp.fi, ret.se += tmp.se;

    }

    return ret;

}

} // namespace CFG.

int main() {

    while (~scanf("%d %d %d", &n, &A, &B) && n | A | B) {

        static int cas = 0; printf("Case %d: ", ++cas);

        rep (i, 1, n) scanf("%s", str[i] + 1), row[i] = col[i] = 0;

        int all = 0, own = 0;

        rep (i, 1, n) rep (j, 1, n) {

            bool f = str[i][j] == '.' || str[i][j] == 'C';

            row[i] += f, col[j] += f, all += f, own += str[i][j] == 'C';

        }

        int ans = -1;

        rep (x, 0, n) {

            CFG::S = 0, CFG::T = n << 1 | 1, CFG::clear();

            rep (i, 1, n) {

                CFG::link(CFG::S, i, row[i], 0);

                CFG::link(i + n, CFG::T, col[i], 0);

                CFG::link(i, i + n, x, 0);

            }

            rep (i, 1, n) rep (j, 1, n) if (str[i][j] == '.') {

                CFG::link(i, j + n, 1, 1);

            }

            PII res(CFG::dinic());

            // printf("%d: %d %d\n", x, res.fi, res.se);

            if (res.fi == all && (all - res.se) * A >= x * B) {

                ans = imax(ans, all - res.se);

            }

        }

        if (~ans) printf("%d\n", ans - own);

        else puts("impossible");

    }

    return 0;

}

巴特西

Solution -「UVA 1104」Chips Challenge

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章