题解归档 - cf104077B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104077B
• 本地来源：problems/cf104077B/idea.md
• 题目链接：https://codeforces.com/gym/104077/problem/B
• 原始标题：B - Cells Coloring

思路

B - Cells Coloring

Empty cells are edges in a bipartite graph (rows, columns). Coloring cells so no two cells in
the same row/column share a color is exactly bipartite edge coloring.

Let D be the maximum degree. By König's line coloring theorem, D colors are sufficient and
necessary.

Only two choices can be optimal:

• use D+1 colors, so color 0 can be unused: cost c*D;
• use exactly D colors: cost c*(D-1) + d*z, where z is the minimum possible size of color
  0.

For the second case, remove the color-0 matching. Every vertex of degree D must be incident to
one removed edge, otherwise its remaining degree is still D and D-1 colors cannot finish the
rest. Thus z is the minimum matching size that covers all maximum-degree vertices.

If R and C are max-degree rows/columns, an edge between a row in R and a column in C covers
two required vertices. Therefore

z = |R| + |C| - maximum_matching(R, C).

Small instances were checked by brute-forcing all proper edge colorings.

代码

来源：problems/cf104077B/solution.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    ll c, d;
    cin >> n >> m >> c >> d;
    vector<string> s(n);
    for (auto &x : s) cin >> x;

    vector<int> rd(n), cd(m);
    int edges = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) if (s[i][j] == '.') {
            rd[i]++;
            cd[j]++;
            edges++;
        }
    }
    int D = 0;
    for (int x : rd) D = max(D, x);
    for (int x : cd) D = max(D, x);
    if (edges == 0) {
        cout << 0 << '\n';
        return 0;
    }

    vector<int> rid(n, -1), cid(m, -1);
    int rn = 0, cn = 0;
    for (int i = 0; i < n; i++) if (rd[i] == D) rid[i] = rn++;
    for (int j = 0; j < m; j++) if (cd[j] == D) cid[j] = cn++;

    vector<vector<int>> g(rn);
    for (int i = 0; i < n; i++) if (rid[i] != -1) {
        for (int j = 0; j < m; j++) if (s[i][j] == '.' && cid[j] != -1) {
            g[rid[i]].push_back(cid[j]);
        }
    }

    vector<int> mt(cn, -1);
    function<bool(int, vector<int>&)> dfs = [&](int v, vector<int> &vis) {
        for (int to : g[v]) if (!vis[to]) {
            vis[to] = 1;
            if (mt[to] == -1 || dfs(mt[to], vis)) {
                mt[to] = v;
                return true;
            }
        }
        return false;
    };
    int match = 0;
    for (int i = 0; i < rn; i++) {
        vector<int> vis(cn);
        if (dfs(i, vis)) match++;
    }

    ll z = rn + cn - match;
    ll ans = min(c * D, c * (D - 1LL) + d * z);
    cout << ans << '\n';
    return 0;
}