P4055 [JSOI2009] 游戏 / YbtOJ「图论」第1章 二分图匹配 F. 游戏 题解--zhengjun
2022/6/29 23:23:07
本文主要是介绍P4055 [JSOI2009] 游戏 / YbtOJ「图论」第1章 二分图匹配 F. 游戏 题解--zhengjun,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
思路
考虑先对各点黑白染色,然后对于相邻的点连边建出二分图。
如果这个二分图有完全最大匹配(即每个点都匹配到了),那么先手必败,因为无论选那个点,后手只要向这个点匹配的另一个点走就行了。
如果是不完全最大匹配,那么先手必胜。
所以先手只要选到不一定在最大匹配中的点开始就一定赢,因为无论接下来后手走到哪里,先手只要跟着走到下一个匹配的点就行了。
所以只要先跑出一种最大匹配,然后从源点汇点分别 dfs 一遍就行了。
代码
#include<bits/stdc++.h> #define edg(i,u) for(int i=head[u],v;v=edge[i].to,i;i=edge[i].nex) using namespace std;typedef long long ll;const int N=5e2+10,M=N*N,K=M*5;char a[N][N]; int n,m,k,s,t,head[M],kk=1,d[M],cur[M],tag[M],ans[M],vis[M];struct edges{int to,c,nex;}edge[K]; void add(int u,int v,int c){edge[++kk]={v,c,head[u]};head[u]=kk;edge[++kk]={u,0,head[v]};head[v]=kk;} int id(int x,int y){return (x-1)*m+y;} bool chk(int x,int y){return x>0&&y>0&&x<=n&&y<=m&&a[x][y]=='.';} bool bfs(){ queue<int>q;q.push(s);memset(d,-1,sizeof d);d[s]=0;cur[s]=head[s];for(int u;!q.empty();q.pop()){ u=q.front();edg(i,u)if(!~d[v]&&edge[i].c)q.push(v),d[v]=d[u]+1,cur[v]=head[v]; }return ~d[t]; } int dfs(int u,int lim=1e9){ if(u==t)return lim;int flow=0;for(int i=cur[u],v;v=edge[i].to,i&&flow<lim;i=edge[i].nex){ cur[u]=i;if(d[v]!=d[u]+1||!edge[i].c)continue;int f=dfs(v,min(lim-flow,edge[i].c)); if(!f)d[v]=-1;edge[i].c-=f;edge[i^1].c+=f;flow+=f; }return flow; } int dinic(){int maxflow=0;for(;bfs();)maxflow+=dfs(s);return maxflow;} void get(int u,int t){if(vis[u])return;vis[u]=1;if(tag[u]+t==2)ans[u]=1;edg(i,u)if(edge[i].c==t)get(v,t);} int main(){ cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i]+1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)k+=a[i][j]=='.'&&(tag[id(i,j)]=((i+j)&1)+1); for(int i=1;i<=n;i++)for(int j=1;j<m;j++)if(a[i][j]=='.'&&a[i][j+1]=='.')(i+j)&1?add(id(i,j+1),id(i,j),1):add(id(i,j),id(i,j+1),1); for(int i=1;i<n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='.'&&a[i+1][j]=='.')(i+j)&1?add(id(i+1,j),id(i,j),1):add(id(i,j),id(i+1,j),1); s=0;t=n*m+1;for(int i=1;i<t;i++)if(tag[i]==1)add(s,i,1);else if(tag[i]==2)add(i,t,1); if(dinic()*2==k)return puts("LOSE"),0;puts("WIN");get(s,1);memset(vis,0,sizeof vis); get(t,0);for(int i=1;i<t;i++)if(tag[i]&&ans[i])printf("%d %d\n",(i-1)/m+1,(i-1)%m+1);return 0; }
这篇关于P4055 [JSOI2009] 游戏 / YbtOJ「图论」第1章 二分图匹配 F. 游戏 题解--zhengjun的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-26React入门教程:从零开始搭建你的第一个React应用
- 2024-12-25Vue2入门教程:轻松掌握前端开发基础
- 2024-12-25Vue3入门指南:快速搭建你的第一个Vue3项目
- 2024-12-25JS基础知识入门教程
- 2024-12-25React基础知识详解:从入门到初级应用
- 2024-12-25Vue3基础知识详解与实战指南
- 2024-12-25Vue3学习:从入门到初步掌握
- 2024-12-25Vue3入门:新手必读的简单教程
- 2024-12-23【JS逆向百例】爱疯官网登录逆向分析
- 2024-12-21Vue3教程:新手入门到实践应用