P5038

jijidawang · 2022-07-16 20:55:13 · 题解

骨牌题考虑黑白染色，设黑白点个数分别为 c_{\sf B}, c_{\sf W}，权值和分别为 s_{\sf B}, s_{\sf W} .

每次操作肯定是恰好操作一个黑点和一个白点，于是设最后所有点都变成了 x，则有 c_{\sf B}\cdot x-s_{\sf B}=c_{\sf W}\cdot x-s_{\sf W}，也即 (c_{\sf B}-c_{\sf W})x=s_{\sf B}-s_{\sf W} .

讨论：

当 c_{\sf B} - c_{\sf W} \neq = 0 时 .
当 c_{\sf B} - c_{\sf W} = s_{\sf B} - s_{\sf W} = 0 时 .
其他情况无解 .

Case 1. 可以解得 x=\dfrac{s_{\sf B}-s_{\sf W}}{c_{\sf B} - c_{\sf W}} .

于是只要判断 x 是否能作为一个解即可，具体见后 .

Case 2. 这表明黑白色块数量相等且权值和相等 .

因为黑白色块数量相等所以如果 x 可以作为一个解那么 x+1 必然也可以 .

也就是解有单调性，二分答案即可 . 判断 x 是否能作为一个解的做法如下：

考虑建立虚拟源汇点 s,t：

所有白点 (i,j) 向 t 连边权为 x-a_{i,j} 的有向边 .
所有黑点 (i,j) 向相邻白点连边权为 +\infty 的有向边 .

因为 x-a_{i,j} 是需要操作的次数，于是因为黑白色块数量权值和相等，如果有解那么流肯定能从 s 流到黑点流到白点再流到 t .

于是只要判断以 s 为源点，t 为汇点的最大流是否等于所有黑点之权值和即可 .

因为是二分图，所以 Dinic 是 O(\sqrt nm) 的 .

这个还不足以作为时间复杂度分析，因为我们没有一个二分答案的上界 .

记 \displaystyle A = \max_i\{a_i\}，设二分图左部为 L，对应的 右部为 R .

则根据最大流定义，有解当且仅当 s 连向 L 的容量和 c_0 不小于 R 连向 t 的容量和 c_1 .

Hall 定理（7.16 闲话）告诉我们，对于任何一个 L，都有 |L|\le |R| .

讨论：

当 |L|=|R| 时，c_0=c_1 .
当 |L|<|R| 时，当答案为 0 时 |c_0-c_1|\le A\cdot nm .

注意到，若答案增加 1，|c_0-c_1| 的 减少量 \Delta\ge |T|-|S|\ge 1 .

于是答案的一个上界为 A\cdot nm .

这样我们知道了答案的一个上界，就可以做复杂度分析了 .

时间复杂度为

\begin{aligned}T(n,m,A)&=O(\sqrt{nm}\cdot nm\cdot\log(A\cdot nm))\\&=O(n^{3/2}m^{3/2}(\log A+\log n+\log m))\\&=O(n^{3/2}m^{3/2}\log\max\{A,n,m\})\end{aligned}

注意到原题数据范围给出 A 的量级远大于 n,m，于是时间复杂度为 O(n^{3/2}m^{3/2}\log A) .

#include <bits/stdc++.h>
template<typename T>
inline T chkmin(T& x, const T& y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, const T& y){if (x < y) x = y; return x;}
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int TD = 44, N = 19198;
const ll INF = 0x3f3f3f3f3f;
struct dinic
{
    struct Node
    {
        int u, v; ll w;
        Node() = default;
        Node(int a, int b, ll c) : u(a), v(b), w(c){}
    };
    vector<Node> e;
    vector<int> g[N];
    inline void addedge(int u, int v, ll w)
    {
        int s = e.size();
        e.emplace_back(Node(u, v, w)); g[u].emplace_back(s++);
        e.emplace_back(Node(v, u, 0)); g[v].emplace_back(s);
    }
    int cur[N], depth[N];
    inline void clear(int n){e.clear(); do g[n].clear(); while (n--);}
    inline bool bfs(int s, int t)
    {
        memset(cur, 0, sizeof cur);
        memset(depth, -1, sizeof depth);
        queue<int> q; q.push(s); depth[s] = 0;
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            for (int ee : g[u])
            {
                int v = e[ee].v;
                if (!~depth[v] && e[ee].w){depth[v] = depth[u] + 1; q.push(v);}
            }
        }
        return ~depth[t];
    }
    ll dfs(int u, int t, ll flow)
    {
        if ((u == t) || (flow <= 0)) return flow;
        ll ans = 0; int s = g[u].size();
        for (int& p = cur[u]; p < s; p++)
        {
            int ee = g[u][p], v = e[ee].v;
            if (depth[u] + 1 != depth[v]) continue;
            ll nxt = dfs(v, t, min(flow, e[ee].w));
            e[ee].w -= nxt; e[ee^1].w += nxt;
            ans += nxt; flow -= nxt;
            if (flow <= 0) break;
        }
        if (ans <= 0) depth[u] = -1;
        return ans;
    }
    inline ll maxflow(int s, int t)
    {
        ll ans = 0;
        while (bfs(s, t)) ans += dfs(s, t, INF);
        return ans;
    }
}F;
int n, m, a[TD][TD];
inline int color(int x, int y){return (x & 1) ^ (y & 1);}
inline int tonode(int x, int y){return x * 40 + y;}
inline bool check(ll x)
{
    int s = tonode(n, m) + 1, t = s + 1;
    F.clear(t);
    ll flow = 0;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            if (color(i, j))
            {
                flow += x - a[i][j];
                F.addedge(s, tonode(i, j), x - a[i][j]);
                if (i > 1) F.addedge(tonode(i, j), tonode(i-1, j), INF); 
                if (j > 1) F.addedge(tonode(i, j), tonode(i, j-1), INF); 
                if (i < n) F.addedge(tonode(i, j), tonode(i+1, j), INF); 
                if (j < m) F.addedge(tonode(i, j), tonode(i, j+1), INF); 
            }
            else F.addedge(tonode(i, j), t, x - a[i][j]);
        }
    return F.maxflow(s, t) == flow;
}
inline void solve()
{
    scanf("%d%d", &n, &m);
    ll b = 0, w = 0; int B = 0, W = 0, M = 0;
    auto readInt = []()
    {
        int ans = 0; char ch;
        while (!isdigit(ch = getchar()));
        do ans = (ans<<3) + (ans<<1) + ch - 48; while (isdigit(ch = getchar()));
        return ans;
    };
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
//          a[i][j] = readInt();
            scanf("%d", a[i] + j);
            chkmax(M, a[i][j]);
            if (color(i, j)){++B; b += a[i][j];}
            else{++W; w += a[i][j];}
        }
    if (B != W)
    {
        ll x = (b - w) / (B - W);
        if ((x >= M) && check(x)) printf("%lld\n", x * W - w);
        else puts("-1");
        return ;
    }
    if (b != w){puts("-1"); return ;}
    ll l = M, r = 3e9, ans = -1;
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid)){r = mid - 1; ans = mid;}
        else l = mid + 1;
    }
    if (!~ans) puts("-1");
    else printf("%lld\n", ans * W - w);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("i.in", "r", stdin);
#endif 
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

</details>