门户网站和部门网站的区别,电子商务网站建设实验总结,wordpress展示页面,仁寿网站建设正题
题目链接:https://www.luogu.com.cn/problem/P4055 题目大意 n∗mn*mn∗m的网格有的不能走#xff0c;走过的不能走。开始有一个棋子先手可以决定位置#xff0c;然后后先手轮流走#xff0c;不能走的就输了#xff0c;求先手的必胜开始位置。 解题思路
我们将图二分…正题
题目链接:https://www.luogu.com.cn/problem/P4055 题目大意
n∗mn*mn∗m的网格有的不能走走过的不能走。开始有一个棋子先手可以决定位置然后后先手轮流走不能走的就输了求先手的必胜开始位置。 解题思路
我们将图二分图染色然后可以走的两两连边。如果这张图有完全匹配那么可以发现无论先手走到哪个点后手可以顺着完全匹配的边走因为这个边一定是先手没有走过的。
如果图没有完全匹配考虑胜负情况。此时对于一个匹配来说图上会有一些点删除后不会影响最大匹配如果先手选择了这些不需要的点作为起点那么后手无论走到哪先手就可以顺着最大匹配的方法走了。
现在问题是考虑如何求出所有最大匹配的不需要点我们可以先跑一遍网络流。然后从源点出发走没有流完的边这些边可以作为当前匹配没有匹配的边或者增广路然后走到的所有左边的点就是答案。而汇点同理走流完的边即可走到的右边的点就是答案。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define p(x,y) ((x)-1)*m(y)
using namespace std;
const int N110*110,inf2147483647/3;
const int dx[4]{1,-1,0,0},dy[4]{0,0,1,-1};
struct node{int to,next,w;
}a[N3];
int n,m,s,t,tot1,ls[N],dep[N],col[N];
bool v[110][110],flag,ans[N];char st[110];
queueint q;
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;return;
}
bool bfs(){while(!q.empty())q.pop();q.push(s);memset(dep,0,sizeof(dep));dep[s]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[y]||!a[i].w)continue;dep[y]dep[x]1;if(yt)return 1;q.push(y);}}return 0;
}
int dinic(int x,int flow){int rest0,k;if(xt)return flow;for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1!dep[y]||!a[i].w)continue;rest(kdinic(y,min(a[i].w,flow-rest)));a[i].w-k;a[i^1].wk;if(restflow)return flow;}if(!rest)dep[x]0;return rest;
}
void dfs(int x,int c){if(dep[x])return;dep[x]1;if(col[x]c)ans[x]flag1;for(int ils[x];i;ia[i].next)if(a[i].wc)dfs(a[i].to,c);return;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%s,st1);for(int j1;jm;j)v[i][j](st[j]#);}s0;tp(n,m)1;col[s]col[t]-1;for(int i1;in;i)for(int j1;jm;j){if(!v[i][j]){if((ij)1)addl(p(i,j),t,1),col[p(i,j)]0;else{addl(s,p(i,j),1),col[p(i,j)]1;for(int k0;k4;k){int xidx[k],yjdy[k];if(x1||y1||xn||ym||v[x][y])continue;addl(p(i,j),p(x,y),1);}}}}while(bfs())dinic(s,inf);memset(dep,0,sizeof(dep)); dfs(s,1);dfs(t,0);if(!flag)return printf(LOSE)0;printf(WIN\n);for(int i1;in;i)for(int j1;jm;j)if(ans[p(i,j)])printf(%d %d\n,i,j);return 0;
}
