题意
sol
第一次做在二分图上博弈的题。。感觉思路真是清奇。。
首先将图黑白染色。
对于某个点,若它一定在最大匹配上,那么bob必胜。因为bob可以一直沿着匹配边都,alice只能走非匹配边。到最后一定是alice不能移动。
否则alice必胜。这个我不会证,但是又举不出反例来qwq。手玩了几个数据发现alice总会有一种方法走某个非匹配边干掉bob。
那么如何找不一定在最大匹配上的点呢?首先求出一个最大匹配,结论是从所有不在最大匹配上的点开始dfs,通过交叉边(目标点的匹配边)走到点都是不一定在最大匹配上的点。(总有一种方案使这个点成为最大匹配)
然后直接匈牙利就行了
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1001, inf = 1e9 + 7, mod = 998244353; template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;} template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;} template <typename a, typename b> inline ll add(a x, b y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;} template <typename a, typename b> inline void add2(a &x, b y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);} template <typename a, typename b> inline ll mul(a x, b y) {return 1ll * x * y % mod;} template <typename a, typename b> inline void mul2(a &x, b y) {x = (1ll * x * y % mod + mod) % mod;} inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m; char s[maxn][maxn]; vector<int> v[maxn * maxn]; void ae(int x, int y) { v[x].push_back(y); v[y].push_back(x); } int vis[maxn * maxn], link[maxn * maxn], tag[maxn * maxn], times; int id(int x, int y) { return (x - 1) * m + y; } bool aug(int x) { for(auto &to : v[x]) { if(vis[to] == times) continue; vis[to] = times;//tag if(!link[to] || aug(link[to])) {link[to] = x; link[x] = to; return 1;} } return 0; } void dfs(int x) { tag[x] = 1; for(auto &to : v[x]) if(!tag[link[to]]) dfs(link[to]); } int main() { n = read(); m = read(); for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(s[i][j] == '.') { if(i < n && s[i + 1][j] == '.') ae(id(i, j), id(i + 1, j)); if(j < m && s[i][j + 1] == '.') ae(id(i, j), id(i, j + 1)); } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(((i + j) & 1) && s[i][j] == '.') times++, aug(id(i, j)); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(s[i][j] == '.' && !link[id(i, j)] && !tag[id(i, j)]) dfs(id(i, j)); int ans = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(tag[id(i, j)]) ans++; cout << ans << 'n'; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(tag[id(i, j)]) cout << i << ' ' << j << 'n'; return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/604805.html