2756: [SCOI2012]奇怪的游戏

Time Limit: 40 Sec Memory Limit: 128 MB

Description

Blinke 最近喜欢上一个奇怪的游戏。这个游戏在一个 N*M的棋盘上玩，每个格子有一个数。每次 Blinker会选择两个相邻的格子，并使这两个数都加上 1。

现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同

一个数则输出-1。

Input

输入的第一行是一个整数T，表示输入数据有T轮游戏组成。

每轮游戏的第一行有两个整数N和M，分别代表棋盘的行数和列数。

接下来有N行，每行 M个数。

Output

对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1。

Sample Input

2 2

1 2

2 3

3 3

1 2 3

2 3 4

4 3 2

Sample Output

-1

HINT【数据范围】

对于30%的数据，保证 T<=10，1<=N,M<=8

对于100%的数据，保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000

题解

首先，我们可以很明显的看出最后形成的数\(x\)一定具有单调性，所以我们可以二分\(x\)。

那么如何写\(check(x)\)呢？

首先我们可以将棋盘黑白染色，之后再将黑色与\(T\)相连，将白色与\(S\)相连，再将黑白色之间连接。这样就可以用一个最大流来解决。

因为每个数字都要变为\(x\)，所以可以将节点与\(S\)或\(T\)相连的边权设为\(x-val\)，之后我们可以将黑白棋子之间的边权设为\(inf\)(其实边权值可以算出，不过由于之前已经限制了边权，所以这里可以不用处理边权)。

因为这个最大流其实就是加了多少次，所以最大流应该等于所有数字与x之差之和的一半。这样，我们就可以写出\(check\)了。

另外，因为\(Cnt[0]*x - Sum[0]=Cnt[1]*x - Sum[1]\)，\(Cnt\)表示黑白棋格的个数，\(Sum\)表示黑白棋格各自的和，所以当\(Cnt[0] \neq Cnt[1]\)时，我们可以直接得出\(x\)，之后直接\(check(x)\)就好了。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int MS = 100000, N = 42;

const LL inl = 1LL << 55;

int ina; char inc, inb[1<<16], *ins = inb, *ine = inb; bool insign;

inline char getc() {

    if (ins == ine) ine = (ins = inb) + fread(inb, 1, 1 << 16, stdin);

    return (ins == ine) ? EOF : *ins++;

}

inline int geti() {

    insign = false;

    while ((inc = getc()) < '0' || inc > '9') insign |= inc == '-'; ina = inc - '0';

    while ((inc = getc()) >= '0' && inc <= '9') ina = (ina << 3) + (ina << 1) + inc - '0';

    return insign ? -ina : ina;

}

int mp[N][N], n, m;

bool col[N][N];

LL Sum[2], Num[2], mv;

namespace CC {

    int To[MS], Nxt[MS], totE, head[N * N], S, T, d[N * N], dt[N * N];

    LL C[MS];

    inline void Adde(int a, int b, LL c) {

        To[totE] = b; Nxt[totE] = head[a]; C[totE] = c; head[a] = totE++;

        To[totE] = a; Nxt[totE] = head[b]; C[totE] = 0; head[b] = totE++;

    }

    const int dx[] = {0,0,-1,1};

    const int dy[] = {1,-1,0,0};

    inline int getp(const int &x, const int &y) { return (x-1)*m + y; }

    LL dfs(int u, LL flow) {

        if (u==T||!flow) return flow;

        LL res = 0, t;

        for (int i = head[u]; ~i; i = Nxt[i])

        if (d[u] == d[To[i]] + 1 && C[i] > 0){

            t = dfs(To[i], min(flow, C[i]));

            C[i] -= t, C[i^1] += t;

            res += t, flow -= t;

            if (!flow) return res;

            if (d[S] > T) return res;

        }

        if (!(--dt[d[u]])) d[S] = T + 1;

        ++dt[++d[u]];

        return res;

    }

    bool check(LL x) {

        memset(head, -1, sizeof head); totE = 0;

        S = 0, T = getp(n, m) + 1;

        LL t, tot = 0, maxflow = 0;

        for (int i = 1; i <= n; ++i)

          for (int j = 1; j <= m; ++j) {

              t = x - mp[i][j];

              if (col[i][j]) Adde(getp(i, j), T, t);

              else Adde(S, getp(i, j), t);

              tot += t;

          }

        for (int i = 1; i <= n; ++i)

          for (int j = 1; j <= m; ++j)

            for (int k = 0; k < 4; ++k) {

                int _i = i + dx[k], _j = j + dy[k];

                if (_i < 1 || _i > n || _j < 1 || _j > m) continue;

                if (!col[i][j]) Adde(getp(i, j), getp(_i, _j), inl);

            }

        memset(d, 0, sizeof d); memset(dt, 0, sizeof dt);

        dt[0] = T + 1;

        while (d[S] < T + 1) maxflow += dfs(S, inl);

        return tot == (maxflow << 1);

    }

}

void init() {

    memset(col, 0, sizeof col);

    n = geti(), m = geti();

    *Sum = Sum[1] = *Num = Num[1] = mv = 0LL;

    bool st = true;

    for (int i = 1; i <= n; ++i)

      for (int j = 1; j <= m; ++j) {

          if ((mp[i][j] = geti()) > mv) mv = mp[i][j];

          col[i][j] = !col[i][j-1];

          if (j <= 1) col[i][j] = (st = !st);

          ++Num[col[i][j]]; Sum[col[i][j]] += mp[i][j];

      }

}

#define getskip(a) (a*n*m - Sum[0] - Sum[1]) >> 1

void Work() {

    if (n * m & 1) {

        LL x = Sum[0] - Sum[1];

        if (x >= mv && CC::check(x)) printf("%lld\n", getskip(x));

        else puts("-1");

    } else {

        LL l = mv, r = inl / 1000, M, ans = -1;

        while (l <= r) {

            M = l + r >> 1;

            if (CC::check(M)) r = (ans = M) - 1;

            else l = M + 1;

        }

        if (~ans) printf("%lld\n", getskip(ans));

        else puts("-1");

    }

}

int main() {

    for (int T = geti(); T; --T) {

        init(); Work();

    }

    return 0;

}

巴特西

bzoj 2756奇怪的游戏