一道甚神但没用到高深模型的题
思路
没思路，看题解吧
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
#define point(x, y) ((x - 1) * m + y)
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const int N = 55, _ = 200005;
const ll inf = 1e16;
int n, m, s, t;
int a[N][N], color[N][N];
ll s1, s2, d1, d2, mx, sum, flow, maxflow;
struct Edge { int Nxt, v; ll flow; } e[_ << 1];
int h[_], p = 1;
void add(int u, int v, ll f) {
e[++p].Nxt = h[u]; e[p].v = v; e[p].flow = f; h[u] = p;
e[++p].Nxt = h[v]; e[p].v = u; e[p].flow = 0; h[v] = p;
}
int d[_];
queue<int> q;
bool bfs() {
memset(d, 0, sizeof(d));
while(!q.empty()) q.pop();
q.push(s); d[s] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = h[u]; i; i = e[i].Nxt)
if(e[i].flow && !d[e[i].v])
{
d[e[i].v] = d[u] + 1;
if(e[i].v == t) return true;
q.push(e[i].v);
}
}
return false;
}
ll dinic(int u, ll flow) {
if(u == t) return flow;
ll rest = flow, k;
for(int i = h[u]; i && rest; i = e[i].Nxt)
if(e[i].flow && d[e[i].v] == d[u] + 1)
{
k = dinic(e[i].v, min(rest, e[i].flow));
if(!k) d[e[i].v] = 0;
e[i].flow -= k;
e[i ^ 1].flow += k;
rest -= k;
}
return flow - rest;
}
bool check(ll x) {
sum = flow = maxflow = 0;
p = 1; memset(h, 0, sizeof(h));
for(int i = 1, tx, ty; i <= n; i++)
for(int j = 1; j <= m; j++)
if(color[i][j] == 0)
for(int k = 0; k < 4; k++)
{
tx = i + dx[k], ty = j + dy[k];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m)
add(point(i, j), point(tx, ty), inf);
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(color[i][j] == 0)
add(s, point(i, j), x - a[i][j]), sum += x - a[i][j];
else
add(point(i, j), t, x - a[i][j]);
while(bfs())
while(flow = dinic(s, inf)) maxflow += flow;
return sum == maxflow;
}
int main()
{
int T = 0;
scanf("%d", &T);
while(T--)
{
mx = s1 = s2 = d1 = d2 = 0;
scanf("%d%d", &n, &m); s = 0, t = n * m + 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d", &a[i][j]), mx = max(mx, 1LL * a[i][j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
color[i][j] = (i + j) & 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(color[i][j] == 0) s1 += a[i][j], d1++;
else s2 += a[i][j], d2++;
if(d1 != d2) {
ll x = (s1 - s2) / (d1 - d2);
if(x >= mx && check(x)) printf("%lld\n", x * d1 - s1);
else printf("-1\n");
}
else {
ll l = mx, r = 1e14, mid = 0, ans = 0;
while(l <= r) {
mid = (l + r) >> 1;
if(check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
if(s1 != s2) printf("-1\n");
else printf("%lld\n", ans * d1 - s1);
}
}
return 0;
}