当前位置:网站首页>【luogu P1971】兔兔与蛋蛋游戏(二分图博弈)
【luogu P1971】兔兔与蛋蛋游戏(二分图博弈)
2022-07-07 02:18:00 【SSL_TJH】
兔兔与蛋蛋游戏
题目链接:luogu P1971
题目大意
给你一个二维网格图,其中只有一个位置没有棋子,其它位置有白棋子或黑棋子。
然后两个人轮流操作,先手可以把空格子旁边四个中的白色棋子选一个移过来,后手则是移动黑色棋子。
然后无法移动者输,然后给你两个人的操作过程,保证后手赢,然后问你有那些时刻由原本先手必胜变成了先手必败。
思路
首先知道二分图博弈的话,你是可以发现这个可以是一个二分图博弈的模型。
(毕竟网格图嘛)
但是状态太多,那我们考虑优化,亦或是合并重复状态,去掉无用状态。
然后你在看两个人交替,而且每个人适用的情况是不同的,然后你又发现其实这个图不大。
那能不能把状态变成图点大小的级别的呢?思考一下会发现一个点不会别重复走。
因为你走出去再回来肯定是经过了偶数次,那这个时候就是另一个人操作来这个点,但是你上一个人走出去把自己的颜色留在了这里,下一个人是进不来的。
那有了这个性质,我们其实就不需要管别的位置的颜色了,只需要直接设状态是空格在什么位置。
然后连边是固定的因为你四周的颜色其实是固定的(得从一个不同颜色的走到这个颜色的,然后那个不同的颜色就相当于被替换成了这个颜色的)
所以就可以搞。
但是你这里不是一次询问,而是你可以理解为每次操作后都要求是否先手必胜(如果先手操作前和操作后这个局面都是先手必胜先手就失误了)。
那你跑那么多次网络流/匈牙利都不太行吧。
那我们考虑一次的时候我们是怎么弄的,我们是先弄删掉点的,然后再弄不删掉的。
那我们这个其实也可以倒序弄,先弄全部删掉的,然后一条一条加上,分别得到答案。
代码
#include<queue>
#include<cstdio>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 45;
char s[N][N];
int n, m, K, tot, S, T;
bool col[N][N], in[N][N], win[2005];
int dx[4] = {
1, 0, -1, 0}, dy[4] = {
0, 1, 0, -1};
pair <int, int> del[2005];
int id(int x, int y) {
return (x - 1) * m + y;}
bool check(int x, int y) {
if (x < 1 || x > n) return 0; if (y < 1 || y > m) return 0; if (col[x][y]) return 0; return 1;}
bool check_(int x, int y) {
if (x < 1 || x > n) return 0; if (y < 1 || y > m) return 0; return 1;}
struct Flow {
struct node {
int x, to, nxt, op;
}e[N * N * 500];
int le[N * N], KK, dis[N * N], lee[N * N];
queue <int> q;
void add(int x, int y, int z) {
e[++KK] = (node){
z, y, le[x], KK + 1}; le[x] = KK;
e[++KK] = (node){
0, x, le[y], KK - 1}; le[y] = KK;
}
bool bfs() {
while (!q.empty()) q.pop();
for (int i = 1; i <= tot; i++) dis[i] = 0, lee[i] = le[i];
q.push(S); dis[S] = 1;
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = le[now]; i; i = e[i].nxt)
if (!dis[e[i].to] && e[i].x) {
dis[e[i].to] = dis[now] + 1;
if (e[i].to == T) return 1;
q.push(e[i].to);
}
}
return 0;
}
int dfs(int now, int sum) {
if (now == T) return sum;
int go = 0;
for (int &i = lee[now]; i; i = e[i].nxt)
if (dis[e[i].to] == dis[now] + 1 && e[i].x) {
int this_go = dfs(e[i].to, min(sum - go, e[i].x));
if (this_go) {
e[i].x -= this_go; e[e[i].op].x += this_go;
go += this_go; if (go == sum) return go;
}
}
return go;
}
int dinic() {
int re = 0;
while (bfs())
re += dfs(S, INF);
return re;
}
}W;
void Init() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (col[i][j] && !in[i][j]) {
for (int k = 0; k < 4; k++) {
int tx = i + dx[k], ty = j + dy[k];
if (!check(tx, ty) || in[tx][ty]) continue;
W.add(id(i, j), id(tx, ty), 1);
}
}
W.dinic();
}
int main() {
scanf("%d %d", &n, &m); tot = id(n, m); S = ++tot; T = ++tot;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
s[i][j] = getchar(); while (s[i][j] != 'X' && s[i][j] != 'O' && s[i][j] != '.') s[i][j] = getchar();
if (s[i][j] == '.') del[0] = make_pair(i, j), in[i][j] = 1;
if (s[i][j] == '.' || s[i][j] == 'X') col[i][j] = 1, W.add(S, id(i, j), 1);
else W.add(id(i, j), T, 1);
}
scanf("%d", &K);
for (int i = 1; i <= K << 1; i++) {
int x, y; scanf("%d %d", &x, &y); del[i] = make_pair(x, y); in[x][y] = 1;
}
Init();
for (int i = K << 1; i >= 0; i--) {
pair <int, int> v = del[i];
in[v.first][v.second] = 0;
for (int j = 0; j < 4; j++) {
int tx = v.first + dx[j], ty = v.second + dy[j];
if (!check_(tx, ty) || in[tx][ty] || col[v.first][v.second] == col[tx][ty]) continue;
if (col[v.first][v.second]) W.add(id(v.first, v.second), id(tx, ty), 1);
else W.add(id(tx, ty), id(v.first, v.second), 1);
}
win[i] = W.dinic();
}
int ans = 0;
for (int i = 1; i <= K << 1; i += 2) {
if (win[i - 1] && win[i]) ans++;
}
printf("%d\n", ans);
for (int i = 1; i <= K << 1; i += 2) {
if (win[i - 1] && win[i]) {
printf("%d\n", (i + 1) / 2);
}
}
return 0;
}
边栏推荐
- 哈趣投影黑馬之姿,僅用半年强勢突圍千元投影儀市場!
- 微信小程序隐藏video标签的进度条组件
- 中英文说明书丨ProSci LAG-3 重组蛋白
- [start from scratch] detailed process of deploying yolov5 in win10 system (CPU, no GPU)
- Party A's requirements for those who have lost 800 yuan
- Developers don't miss it! Oar hacker marathon phase III chain oar track registration opens
- Software testing knowledge reserve: how much do you know about the basic knowledge of "login security"?
- 【OpenCV】形态学滤波(2):开运算、形态学梯度、顶帽、黑帽
- 基本Dos命令
- Symmetric binary tree [tree traversal]
猜你喜欢
哈趣投影黑马之姿,仅用半年强势突围千元投影仪市场!
Ha Qu projection dark horse posture, only half a year to break through the 1000 yuan projector market!
请问如何查一篇外文文献的DOI号?
tkinter窗口选择pcd文件并显示点云(open3d)
Go straight to the 2022ecdc fluorite cloud Developer Conference: work with thousands of industries to accelerate intelligent upgrading
力扣62 不同路径(从矩阵左上到右下的所有路径数量) (动态规划)
"Parse" focalloss to solve the problem of data imbalance
屏幕程序用串口无法调试情况
【OpenCV】形态学滤波(2):开运算、形态学梯度、顶帽、黑帽
学习笔记|数据小白使用DataEase制作数据大屏
随机推荐
怎样查找某个外文期刊的文献?
隐马尔科夫模型(HMM)学习笔记
[FPGA] EEPROM based on I2C
C language interview to write a function to find the first occurrence of substring m in string n.
Doctoral application | Professor Hong Liang, Academy of natural sciences, Shanghai Jiaotong University, enrolls doctoral students in deep learning
JMeter function assistant - random value, random string, fixed value random extraction
The difference between string constants and string objects when allocating memory
缓存在高并发场景下的常见问题
屏幕程序用串口无法调试情况
Go straight to the 2022ecdc fluorite cloud Developer Conference: work with thousands of industries to accelerate intelligent upgrading
Pinduoduo lost the lawsuit: "bargain for free" infringed the right to know but did not constitute fraud, and was sentenced to pay 400 yuan
POI导出Excel:设置字体、颜色、行高自适应、列宽自适应、锁住单元格、合并单元格...
精准时空行程流调系统—基于UWB超高精度定位系统
Redis(一)——初识Redis
HKUST & MsrA new research: on image to image conversion, fine tuning is all you need
Audio distortion analysis of DSP and DAC based on adau1452
谷歌 Chrome 浏览器发布 103.0.5060.114 补丁修复 0-day 漏洞
Install mongodb database
CloudCompare-点对选取
Overview of FlexRay communication protocol