B. Cells Coloring

题意

给出$n \times m$个格子，其中有障碍物，要求你将网格涂色，你可以指定一个数字$k$，表示你将使用$0 \dots k$的数字来填涂网格，若你使用$1 \dots k$的数字涂色，那么每一行或者每一列相同的颜色的格子最多只能有一个，若你使用数字$0$来涂色，那么没有任何设置。

给出两个数字$c、d$，当你确定了一种填涂方案，那么该方案的费用为$c \cdot k + d \cdot z$，$z$ 代表你使用的数字$0$的个数，请你最小化这个费用，并输出最小费用。

思路

当读完题目之后以及看了眼数据范围，基本可以确定是一道网络流的题目。但是最后求的那个式子不是很好转化到边权上，并且$k$是未知的，但是当我们确定了$k$的值后，我们可以利用最大流求出这$k$种颜色最多能覆盖多少个网格，然后剩余的格子就是用$0$来填涂的。所以我们考虑枚举$k$，然后取最大值，但是这题时限只有1s，所以我们考虑优化，通过本地枚举$k$来求式子发现，这个式子是个随$k$的增大先减后增的函数，所以我们考虑三分$k$，极小值点的$k$即为最小值里的$k$。

关于怎么建图，可以参考代码。

截屏2022-11-30 17.13.14

$TLE$的是暴力枚举的结果，$WA$的是三分但是图建错的结果，感觉太久没写网络流，脑子有点转不动了qwq

代码

#include<bits/stdc++.h>
using LL = long long;

constexpr int INF = 0x3f3f3f3f;
template< typename T >
struct Edge {
    int from, to;
    T cap, flow;

    Edge(int u, int v, T c, T f) : from(u), to(v), cap(c), flow(f) {}
};
template< typename T >
struct Dinic {
    int n, m;
    int Source, Sink;
    std::vector< Edge< T > > edges;
    std::vector< std::vector< int > > G;
    std::vector< int > d, cur;
    std::vector< bool > vis;

    // number of vertices
    Dinic(int n) : n(n), d(n), cur(n), vis(n), G(n) {}
    
    void AddEdge(int from, int to, T cap) {
        edges.push_back(Edge< T >(from, to, cap, 0));
        edges.push_back(Edge< T >(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool BFS() {
        vis.assign(n, 0);
        std::queue< int > Q;
        Q.push(Source);
        d[Sink] = 0;
        vis[Source] = true;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < G[x].size(); ++ i) {
                Edge< T > &e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[Sink];
    }

    T DFS(int x, T a) {
        if (x == Sink || a == 0) {
            return a;
        }
        T flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); ++ i) {
            Edge< T > &e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, std::min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) {
                    break;
                }
            }
        }
        return flow;
    }

    T Maxflow(int s, int t) {
        this->Source = s;
        this->Sink = t;
        T flow = 0;
        while (BFS()) {
            cur.assign(n, 0);
            flow += DFS(Source, INF);
        }
        return flow;
    }
};
int n, m, c, d;
std::string s[300];
LL calc(int k) {
    Dinic< LL > F(n + n * m + m + 2);
    int S = n + n * m + m, T = S + 1;
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            if (s[i][j] == '.') {
                F.AddEdge(n * m + i, i + j * n, 1);
                F.AddEdge(i + j * n, n * m + n + j, 1);
            }
        }
    }
    for (int i = 0; i < n; ++ i) {
        F.AddEdge(S, n * m + i, k);
    }
    for (int i = 0; i < m; ++ i) {
        F.AddEdge(n * m + n + i, T, k);
    }
    return F.Maxflow(S, T);
}
int all = 0;
LL f(int num, int k) {
    return 1LL * (all - num) * d + 1LL * k * c;
}
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    #ifndef ONLINE_JUDGE
    freopen("Input.in", "r", stdin);
    freopen("Output.out", "w", stdout);
    #endif

    std::cin >> n >> m >> c >> d;
    for (int i = 0; i < n; ++ i) {
        std::cin >> s[i];
        for (int j = 0; j < m; ++ j) {
            if (s[i][j] == '.') {
                ++ all;
            }
        }
    }
    int ans;
    int L = 0, R = n + m;
    while (L <= R) {
        int mid = (R - L) / 3, lmid = L + mid, rmid = R - mid;

        if (f(calc(lmid), lmid) > f(calc(rmid), rmid)) {
            L = lmid + 1;
        } else {
            R = rmid - 1;
            ans = rmid;
        }
    }
    std::cout << f(calc(ans), ans) << '\n';
    return 0;
}