当前位置:网站首页>[Luogu p1971] rabbit and egg game (bipartite game)
[Luogu p1971] rabbit and egg game (bipartite game)
2022-07-07 07:04:00 【SSL_ TJH】
Rabbit and egg game
Topic link :luogu P1971
The main idea of the topic
Give you a two-dimensional grid , There is only one position without chess pieces , There are white or black pieces in other positions .
Then two people take turns , The first hand can move one of the four white chess pieces next to the empty grid , The back hand moves the black chess pieces .
Then those who cannot move lose , Then give you the operation process of two people , Guarantee the backhand to win , Then I ask you what moments have changed from being the first to win to being the first to lose .
Ideas
First of all, if you know the bipartite graph game , You can find that this can be a bipartite graph game model .
( After all, the grid diagram )
But there are too many states , Let's consider optimization , Or merge duplicate States , Get rid of useless state .
Then you are watching two people alternate , And everyone applies to different situations , Then you find that this picture is not big .
Can we change the state to the level of graph point size ? Think about it and you'll find a point. Don't repeat it .
Because you must go out and come back after an even number of times , At this time, another person operates to this point , But you last went out and left your color here , The next person can't get in .
Then with this property , In fact, we don't need to care about the color of other positions , Just set the position of the space directly .
Then the edges are fixed, because the colors around you are actually fixed ( We have to go from a different color to this color , Then the different color is equivalent to being replaced with this color )
So we can do it .
But this is not an inquiry , But you can understand it as asking whether to win first after each operation ( If the situation before and after the first hand operation is that the first hand will win, the first hand will make a mistake ).
Then you run so many network flows / Hungary is not very good .
When we think about it once, how did we do it , We deleted some first , Then you can't delete it .
In fact, we can do this in reverse order , First get all deleted , Then add one by one , Get the answers respectively .
Code
#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;
}
边栏推荐
- 如何给目标机器人建模并仿真【数学/控制意义】
- MATLAB小技巧(30)非线性拟合 lsqcurefit
- RuntimeError: CUDA error: CUBLAS_STATUS_ALLOC_FAILED when calling `cublasCreate(handle)`问题解决
- Mysql---- import and export & View & Index & execution plan
- .net 5 FluentFTP连接FTP失败问题:This operation is only allowed using a successfully authenticated context
- 企業如何進行數據治理?分享數據治理4個方面的經驗總結
- 栈题目:有效括号的嵌套深度
- impdp的transform参数的测试
- How to do sports training in venues?
- 算法---比特位计数(Kotlin)
猜你喜欢
2022年全国所有A级景区数据(13604条)
Basic introduction of JWT
. Net core accesses uncommon static file types (MIME types)
Anr principle and Practice
SolidWorks的GB库(钢型材库,包括铝型材、铝管等结构)安装及使用教程(生成铝型材为例)
2018 Jiangsu Vocational College skills competition vocational group "information security management and evaluation" competition assignment
Brand · consultation standardization
Mysql---- import and export & View & Index & execution plan
[noi simulation] regional division (conclusion, structure)
化工园区危化品企业安全风险智能化管控平台建设四大目标
随机推荐
Master-slave replication principle of MySQL
From zero to one, I will teach you to build the "clip search by text" search service (2): 5 minutes to realize the prototype
libcurl返回curlcode说明
一条慢SQL拖死整个系统
大咖云集|NextArch基金会云开发Meetup来啦
大促过后,销量与流量兼具,是否真的高枕无忧?
toRefs API 与 toRef Api
Maze games based on JS
.net 5 FluentFTP连接FTP失败问题:This operation is only allowed using a successfully authenticated context
2022/07/04学习记录
Redhat5 installing vmware tools under virtual machine
JWT的基础介绍
How DHCP router works
途家、木鸟、美团……民宿暑期战事将起
请教一下,监听pgsql ,怎样可以监听多个schema和table
Matlab tips (30) nonlinear fitting lsqcurefit
The startup of MySQL installed in RPM mode of Linux system failed
Bus消息总线
Initial experience of addresssanitizer Technology
Data of all class a scenic spots in China in 2022 (13604)