bzoj 1443 二分图博弈
2024-08-24 20:37:07
这种两个人轮流走,不能走 走过的格子的大都是二分图博弈。。。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>
#define y1 skldjfskldjg
#define y2 skldfjsklejg using namespace std; const int N = + ;
const int M = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +; int n, m, tot, hs[N][N], match[N * N], f[N * N], ans[N * N];
int dx[] = {, }, dy[] = {, };
bool vis[N * N];
vector<int> edge[N * N];
char s[N][N]; int path(int u) {
for(int i = ; i < edge[u].size(); i++) {
int v = edge[u][i];
if(!vis[v]) {
vis[v] = true;
if(match[v] == - || path(match[v])) {
match[v] = u;
return ;
}
}
}
return ;
} void work(int u) {
if(ans[u]) return;
ans[u] = ;
for(int i = ; i < edge[u].size(); i++) {
int v = edge[u][i];
if(match[v] != -) work(match[v]);
}
} int main() {
memset(match, -, sizeof(match));
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) scanf("%s", s[i] + ); for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(s[i][j] == '#') continue;
hs[i][j] = ++tot;
f[hs[i][j]] = (i ^ j) & ;
}
} for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(s[i][j] == '#') continue;
for(int k = ; k < ; k++) {
int x = i + dx[k], y = j + dy[k];
if(hs[x][y]) {
edge[hs[i][j]].push_back(hs[x][y]);
edge[hs[x][y]].push_back(hs[i][j]);
}
} }
} int cnt = ;
for(int i = ; i <= tot; i++) {
if(f[i]) {
memset(vis, , sizeof(vis));
if(path(i)) cnt++;
}
}
if( * cnt == tot) {
puts("LOSE");
} else {
puts("WIN");
for(int i = ; i <= tot; i++) {
if(match[i] != -) match[match[i]] = i;
}
for(int i = ; i <= tot; i++) {
if(match[i] == -) work(i);
} for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(ans[hs[i][j]]) printf("%d %d\n", i, j);
}
}
}
return ;
} /*
*/
最新文章
- (转)SVN服务器搭建和使用(二)
- 第三波假期干货——webstrom工具栏图标
- Linux - 常用Shell命令
- css加阴影
- JS&;CSS文件请求合并及压缩处理研究(一)
- 深入理解Java String#intern() 内存模型
- Lucene学习笔记: 五,Lucene搜索过程解析
- SNMP协议总结
- 2.2.5 NIO.2 Path 和 Java 已有的 File 类
- setTimeout()与setInterval() 问题
- 分享几个有意思的css js工具网站
- flask 手机号码正则匹配的简单操作
- 【Windows】+ windows下在某一文件夹下按“shift+鼠标右键”打开CMD窗口
- Mac 下 软件安装路径查看 命令: Which, 估计Linux 也是
- Java 容器之 Connection栈队列及一些常用
- 在ASP.NET Core上实施每个租户策略的数据库
- Android几行代码实现监听微信聊天
- MySQL 5.6 Replication 复制 FAQ
- 九度 1494:Dota(完全背包)
- Discoverer Table