1 条题解
-
0
骨牌题考虑黑白染色，设黑白点个数分别为 ，权值和分别为 .
每次操作肯定是恰好操作一个黑点和一个白点，于是设最后所有点都变成了 ，则有 $c_{\sf B}\cdot x-s_{\sf B}=c_{\sf W}\cdot x-s_{\sf W}$，也即 .
讨论：
- 当 时 .
- 当 时 .
- 其他情况无解 .
Case 1. 可以解得 $x=\dfrac{s_{\sf B}-s_{\sf W}}{c_{\sf B} - c_{\sf W}}$ .
于是只要判断 是否能作为一个解即可，具体见后 .
Case 2. 这表明黑白色块数量相等且权值和相等 .
因为黑白色块数量相等所以如果 可以作为一个解那么 必然也可以 .
也就是解有单调性，二分答案即可 . 判断 是否能作为一个解的做法如下：
考虑建立虚拟源汇点 ：
- 向所有黑点 连边权为 的有向边 .
- 所有白点 向 连边权为 的有向边 .
- 所有黑点 向相邻白点连边权为 的有向边 .
因为 是需要操作的次数，于是因为黑白色块数量权值和相等，如果有解那么流肯定能从 流到黑点流到白点再流到 .
于是只要判断以 为源点， 为汇点的最大流是否等于所有黑点之权值和即可 .
因为是二分图，所以 Dinic 是 的 .
这个还不足以作为时间复杂度分析，因为我们没有一个二分答案的上界 .
记 ，设二分图左部为 ，对应的 右部为 .
则根据最大流定义，有解当且仅当 连向 的容量和 不小于 连向 的容量和 .
Hall 定理（7.16 闲话）告诉我们，对于任何一个 ，都有 .
讨论：
-
当 时， .
-
当 时，当答案为 时 .
注意到，若答案增加 ， 的 减少量 .
于是答案的一个上界为 .
这样我们知道了答案的一个上界，就可以做复杂度分析了 .
时间复杂度为
$$\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}$$注意到原题数据范围给出 的量级远大于 ，于是时间复杂度为 .
Code
#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; }
- 1
