[LOJ2447.] 「NOI2011」兔兔与蛋蛋的游戏

[LOJ2447.] 「NOI2011」兔兔与蛋蛋的游戏

题目链接

当我入梦,这个世界就将颤抖

Solution

我们将原问题的操作改为

兔兔每次操作将空格和一个相邻白色的棋子交换位置
蛋蛋每次操作将空格和一个相邻黑色的棋子交换位置

我们考虑这个空格的移动路线

对于兔兔的第一次操作,空格和可以走到周围的白色棋子
之后空格可以走到周围的黑色棋子
……

我们发现空格可以到达的位置一定是经过 兔蛋兔蛋兔蛋 这样子的交替路

我们考虑什么时候兔兔可以赢,就是当且仅当对于每一个可行的路径都是兔后无蛋的时候
否则蛋蛋可以经过一次操作将路径改变为兔后有蛋

这样子就是经过了奇数次的交换
我们发现二分图的一个增光路是经过奇数次的交换的

不妨对这个棋子进行黑白染色
我们将两个相邻的并且棋子类型是不同的连边
兔兔能赢当且仅当空格一定是在最大匹配上

什么时候兔兔输呢,我们考虑空格如果不在最大匹配上,那么其相邻的点一定在最大匹配上(这是显然的),那么按照上述推论那么蛋蛋接下来必赢qwq

那么我们怎么找一个点是否一定在最大匹配上呢,我们发现路径不能交叉,那么我们只需要标记当前这个点是不可以被匹配的,然后跑一遍二分图匹配匹配这个点所匹配的点,如果有增广路则说明这不是必赢的。

Code

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>

using namespace std;

inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    do {x = x * 10 + (c ^ 48); c = getchar();} while(isdigit(c));
    return x * f;
}

const int N = 58 ;
struct E {
    int nxt, to;
} edg[N * N * 4];
int head[N * N], id[N][N], a[N][N];
char s[N];
int n, m, gx, gy, x, y, cnt, num, tot;
bool visit[N * N], ban[N * N];
int ans[N * N]; 
int links[N * N], res[N * N * 2];

void add(int from, int to) {
    static int qwq = 0;
    edg[++qwq] = (E) {head[from], to};
    head[from] = qwq;
}

void build_edge(int u, int v) {
    add(u, v); add(v, u);
}

bool dfs(int u) {
    for(int i = head[u]; ~i; i = edg[i].nxt) {
        int v = edg[i].to;
        if(visit[v] || ban[v]) continue;
        visit[v] = true;
        if(!links[v] || dfs(links[v])) {
            links[v] = u; links[u] = v;
            return true;
        }
    }
    return false;
}

int main() {
    n = read(), m = read();
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        for(int j = 1; j <= m; ++j) {
            if(s[j] == 'X') a[i][j] = 1;
            else if(s[j] == 'O') a[i][j] = 2;
            else if(s[j] == '.') { 
                a[i][j] = 1;
                gx = i; gy = j;
            }
        }
    }
    int pos = (gx + gy) & 1;
    for(int i = 1; i <= n; ++i) 
        for(int j = 1; j <= m; ++j) {
            if(a[i][j] == 2 && (((i + j) & 1) != pos)) {
                id[i][j] = ++tot;
            } else {
                if(a[i][j] == 1 && (((i + j) & 1) == pos)) {
                    id[i][j] = ++tot;
                } else continue;
            }
            if(id[i - 1][j]) build_edge(id[i][j], id[i - 1][j]);
            if(id[i][j - 1]) build_edge(id[i][j], id[i][j - 1]);
        }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(id[i][j] && a[i][j] == 2) {
                memset(visit, false, sizeof(visit));
                dfs(id[i][j]);
            }
    int gk = read(); x = gx, y = gy;
    for(int i = 1; i <= gk * 2; ++i) {
        ban[id[x][y]] = true;
        if(links[id[x][y]] && id[x][y]) {
            int tmp = links[id[x][y]];
            links[id[x][y]] = links[tmp] = 0;
            memset(visit, false, sizeof(visit));
            res[i] = !dfs(tmp);
        }
        x = read(), y = read();
    }
    for(int i = 1; i <= gk; ++i)
        if(res[(i * 2) - 1] && res[i * 2]) ans[++num] = i;
    printf("%d\n", num);
    for(int i = 1; i <= num; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

2
说点什么

avatar
1 Comment threads
1 Thread replies
1 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
DefFrancis Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
DefFrancis
游客
DefFrancis

垃圾代码怎么写出来的???

DefFrancis
游客

我承认,是我发的,是我瞧不起mxg