产品服务展示型网站有哪些,做网站学习,广州婚恋网站排名,用dreamware制作网页传送门
显然是个二分图#xff0c;设开始位置是左边#xff0c;另一边是右边
那么先手是把左边挪到右边#xff0c;后手是把右边挪到左边#xff0c;不能挪的那方失败
结论#xff1a;Alice必胜当且仅当开始位置不一定在最大匹配上
必要性#xff1a;
如果开始位置不…传送门
显然是个二分图设开始位置是左边另一边是右边
那么先手是把左边挪到右边后手是把右边挪到左边不能挪的那方失败
结论Alice必胜当且仅当开始位置不一定在最大匹配上
必要性
如果开始位置不在最大匹配上那一定有种匹配方案不包含开始位置废话
考虑这种方案由于左边已经空出来了所以右边和它连通的点都已经有匹配。
这样Bob移动到哪里Alice就移到它的匹配点这样Alice必胜。
充分性
考虑逆否命题如果开始位置一定在最大匹配上那么Bob必胜。
①如果右边有和开始位置相邻的未匹配点
Bob移到这个位置然后转换为了上面的情况
②如果没有
那就移到匹配点
因为开始点一定在最大匹配上所以移了之后找不到未匹配点
同理后面如果左边有未匹配点就找到了一条增广路矛盾
这样可以一直走匹配点直到胜利
所以先跑个最大匹配从未匹配点开始dfs对所有与之相邻点给匹配点打上标记
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 10005
#define MAXM 50005
using namespace std;
struct edge{int u,v;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
void addnode(int u,int v)
{e[cnt](edge){u,v};nxt[cnt]head[u];head[u]cnt;
}
int n,m;
char s[105][105];
#define id(x,y) (((x)-1)*m(y))
const int dx[]{-1,1,0,0},dy[]{0,0,-1,1};
int link[MAXN],used[MAXN];
bool find(int u,int mark)
{for (int ihead[u];i;inxt[i])if (used[e[i].v]!mark){used[e[i].v]mark;if (!link[e[i].v]||find(link[e[i].v],mark)) return link[e[i].v]u,true;}return false;
}
bool ans[MAXN];
void dfs(int u)
{for (int ihead[u];i;inxt[i])if (!ans[link[e[i].v]]){ans[link[e[i].v]]true;dfs(link[e[i].v]);}
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i) scanf(%s,s[i]1);for (int x1;xn;x)for (int y1;ym;y)if (s[x][y].(xy)1)for (int i0;i4;i)if (s[xdx[i]][ydy[i]].)addnode(id(x,y),id(xdx[i],ydy[i]));int d0;for (int x1;xn;x)for (int y1;ym;y)if (s[x][y].(xy)1)dfind(id(x,y),id(x,y)),ans[id(x,y)]1;cerrdendl;for (int x1;xn;x)for (int y1;ym;y)if (s[x][y].!((xy)1))link[id(x,y)]? ans[link[id(x,y)]]0,link[link[id(x,y)]]id(x,y):ans[id(x,y)]1;int tcntcnt;for (int i1;itcnt;i) addnode(e[i].v,e[i].u);for (int i1;in*m;i) if (ans[i]) dfs(i);int tot0;for (int x1;xn;x)for (int y1;ym;y)totans[id(x,y)];printf(%d\n,tot);for (int x1;xn;x)for (int y1;ym;y)if (ans[id(x,y)])printf(%d %d\n,x,y);return 0;
}
