bzoj 2437 [Noi2011]兔子和鸡蛋 [二分图匹配]

2022-12-29 21:34:01

叙述性说明

这些日子。兔子和蛋像一个新的棋盘游戏。

这场比赛是在 n 行 m 在船上进行列。

前，棋盘上有一

个格子是空的，其他的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。

每一局游戏总是兔兔先操作。之后两方轮流操作。详细操作为：

兔兔每次操作时，选择一枚与空格相邻的白色棋子，将它移进空格。

蛋蛋每次操作时，选择一枚与空格相邻的黑色棋子，将它移进空格。

第一个不能依照规则操作的人输掉游戏。

近期兔兔总是输掉游戏，并且蛋蛋格外嚣张，于是兔兔想请她的好朋友——

你——来帮助她。

她带来了一局输给蛋蛋的游戏的实录。请你指出这一局游戏中

全部她“犯错误”的地方。

注意：

两个格子相邻当且仅当它们有一条公共边。

兔兔的操作是“犯错误”的。当且仅当。在这次操作前兔兔有必胜策略。

而这次操作后蛋蛋有必胜策略。

格式

输入格式

输入的第一行包括两个正整数 n、m。

接下来 n行描写叙述初始棋盘。当中第i 行包括 m个字符。每一个字符都是大写英

文字母"X"、大写英文字母"O"或点号"."之中的一个。分别表示相应的棋盘格中有黑色

棋子、有白色棋子和没有棋子。

当中点号"."恰好出现一次。

接下来一行包括一个整数 k（1≤k≤1000） ，表示兔兔和蛋蛋各进行了k次操

作。

接下来 2k行描写叙述一局游戏的过程。

当中第 2i – 1行是兔兔的第 i 次操作（编

号为i的操作） ，第2i行是蛋蛋的第i次操作。每一个操作使用两个整数x,y来描写叙述。

表示将第x行第y列中的棋子移进空格中。

输入保证整个棋盘中仅仅有一个格子没有棋子， 游戏过程中兔兔和蛋蛋的每一个

操作都是合法的。且最后蛋蛋获胜。

输出格式

输出文件的第一行包括一个整数r。表示兔兔犯错误的总次数。

接下来r 行按递增的顺序给出兔兔“犯错误”的操作编号。

当中第 i 行包括

一个整数ai表示兔兔第i 个犯错误的操作是他在游戏中的第 ai次操作。

例子1

例子输入1

1 6

XO.OXO

1

1 2

1 1

例子输出1

1

1

例子2

例子输入2

例子输出2

例子3

例子输入3

4 4

OOXX

OXXO

OO.O

XXXO

2

3 2

2 2

1 2

1 3

例子输出3

提示

1~2: n=1, 1<=m<=20

3: n=3, m=4

4~5: n=4, m=4

6~7: n=4, m=5

8: n=3, m=7

9~14: n=2, 1<=m<=40

15~16: 1<=n<=16, 1<=m<=16

17~20: 1<=n<=40, 1<=m<=40

Solution

能够看做是将空格依照黑白交替的方式移动。

先把格子黑白染色，最好还是令起点为黑色，相邻且颜色不同的格子连边。连边时注意。假设起点坐标为(x,y)。且(x+y)%2=0。则仅仅有相同横纵坐标之和为奇数的黑格子才实用。

假设起点在一定最大匹配中，则一定先手必胜。由于起点一定在奇数边的交错轨中。仅仅要每次都沿着匹配的边走，一定能够赢。

假设起点不一定在最大匹配中，则后手必胜。由于第一步走到的点，一定在不包括起点的最大匹配中。

所以仅仅要当前点一定在最大匹配中就是必胜态，假设走之前是必胜态，走之后还是必胜态。那么说明这一步就走错了。

#include <bits/stdc++.h>

using namespace std;

int n, m;

int arr[45][45];

int tot;

int x, y;

int num[45][45];

vector<int> edges[10005];

bool vis[10005], ban[10005];

int mat[10050];

bool dfs(int i) {

    if (ban[i]) return false;

    for (int j = 0; j < edges[i].size(); j++) {

        int k = edges[i][j];

        if (!vis[k] && !ban[k]) {

            vis[k] = 1;

            if (!mat[k] || dfs(mat[k])) {

                mat[k] = i;

                mat[i] = k;

                return true;

            }

        }

    }

    return false;

}

int ans[10005];

int main() {

    scanf("%d %d", &n, &m);

    char str[45];

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

        scanf("%s", str + 1);

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

            if (str[j] == 'O') arr[i][j] = 1;

            else if (str[j] == 'X') arr[i][j] = 2;

            else arr[i][j] = 2, x = i, y = j;

        }

    }

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

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

            if (arr[i][j] == 1 ^ (((i + j) & 1) == ((x + y) & 1)))

                num[i][j] = ++tot;

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

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

            if (!num[i][j]) continue;

            if (num[i + 1][j]) {

                edges[num[i][j]].push_back(num[i + 1][j]);

                edges[num[i + 1][j]].push_back(num[i][j]);

            }

            if (num[i][j + 1]) {

                edges[num[i][j]].push_back(num[i][j + 1]);

                edges[num[i][j + 1]].push_back(num[i][j]);

            }

        }

    }

    for (int i = 1; i <= tot; i++) {

        memset(vis, 0, sizeof(vis));

        if (!mat[i]) dfs(i);

    }

    int k;

    scanf("%d", &k);

    for (int i = 1; i <= k << 1; i++) {

        int fuck = num[x][y];

        ban[fuck] = 1;

        if (mat[fuck]) {

            int match = mat[fuck];

            mat[match] = mat[fuck] = 0;

            memset(vis, 0, sizeof(vis));

            ans[i] = (!dfs(match));

        }

        scanf("%d %d", &x, &y);

    }

    int res = 0;

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

        res += (ans[i * 2 - 1] & ans[i * 2]);

    printf("%d\n", res);

    for (int i = 1; i <= k; i++) {

        if (ans[i * 2 - 1] & ans[i * 2]) {

            printf("%d\n", i);

        }

    }

    return 0;

}

码农公寓