http://www.zybbs.org/JudgeOnline/problem.php?id=1443

这题囧翻了，WA到实在受不了了去找Delostik神犇的代码然后几乎改得一模一样了还是WA。无奈下对拍，结果发现==比&先算……加个括号果断AC。不过时间只排了第十，第一的那个15MS怎么弄出来的……

做法很简单……黑白染色后构二分图然后判断没一个点是否必在最大匹配里……但是怎么输出WIN的位置想了好久，看了WJMZBMR神犇的题解也稀里糊涂，后来画了几张图看看好像又有点感觉了，再去看题解觉得好像是对的，看代码发现真的是对的……就是在残量网络上从S开始DFS一遍能DFS到的左边的点，和把边反向DFS一遍能DFS到的右边的点都是W位置。至于为什么是对的……呃……我反正证不出来，看看好象是对的就写了。我果然是苣蒻……

我想了一下，大致是这样的：假设用匈牙利算法，跑出来以后观察所有左边的点，不在最大匹配中的必定可以不在最大匹配中（废话），对这些点继续DFS，所有能DFS到的左边的点必定可以通过这条DFS路增广使得这个点不在最大匹配中（已经是最大匹配了，如果能增广只可能将匹配数增加0）……右边也一样……但是由于构图原因所以右边的点DFS时需要把边反向（相当于反过来匈牙利一下）。

我的2B代码……（最近好像萌上了狂交……AC(5)都不罢休……我难道被Oleg带坏了么？）

#include <stdio.h>
__inline getint(){
	int re=0,ch=getchar(),k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}int m,s,t,dis[10002],gap[30001],flow=0,delta,x=0,i,j,stp=0,N,M,win[10002],v[10002],all=-1;
char str[100][101];
struct edge{int x,y,w;struct edge *opp,*next;}*map[10002],*neck[10002],*from[10002],*cur[10002],st[60000],*f;
__inline void ADDEDGE(x,y){
	st[stp].next=map[st[stp^1].y=st[stp].x=x];
	st[stp^1].next=map[st[stp].y=st[stp^1].x=y];
	(st[stp^1].opp=map[x]=st+stp)->w=1;st[stp].opp=map[y]=st+(stp^1);
	stp+=2;
}void dfs(x){
	struct edge *p=map[x];
	if((((x%M^x/M))&1)==i)all++,win[x]=1;//就是这里这个括号……被搞死了
	for(v[x]=1;p;p=p->next)if(p->w==i&&!v[p->y])dfs(p->y);
}main(){
	gap[m]=(N=getint())*(M=getint())+2;s=N*M;t=s+1;
	for(i=0;i<N;i++)gets(str[i]);
	for(i=0;i<N;i++)for(j=0;j<M;j++,x++){
		if(str[i][j]=='#')continue;
		if((i^j)&1){
			ADDEDGE(s,x);
			if(i&&str[i-1][j]=='.')ADDEDGE(x,x-M);
			if(j&&str[i][j-1]=='.')ADDEDGE(x,x-1);
			if(i!=N-1&&str[i+1][j]=='.')ADDEDGE(x,x+M);
			if(j!=M-1&&str[i][j+1]=='.')ADDEDGE(x,x+1);
		}else ADDEDGE(x,t);
	}for(m=stp>>1,i=s;dis[s]<=m;){
		for(cur[i]||(cur[i]=map[i]);cur[i];cur[i]=cur[i]->next)if(cur[i]->w&&dis[cur[i]->y]+1==dis[i]){
			neck[(from[cur[i]->y]=cur[i])->y]=s==i?cur[i]:neck[i]->w>cur[i]->w?cur[i]:neck[i];
			if(t==(i=cur[i]->y)){
				for(flow+=delta=neck[t]->w;i!=s;i=from[i]->x)from[i]->w-=delta,from[i]->opp->w+=delta;
				i=neck[t]->x;
			}break;
		}if(!cur[i]){
			if(!--gap[dis[i]])break;
			for(dis[i]=m,f=map[i];f;f=f->next)if(f->w&&dis[f->y]<dis[i])dis[i]=dis[(cur[i]=f)->y];
			gap[++dis[i]]++;
			i=i==s?s:from[i]->x;
		}
	}i=1;dfs(s);i=0;dfs(t);
	if(all){
		puts("WIN");
		for(;i<s;i++)if(win[i])printf("%d %d\n",i/M+1,i%M+1);
	}else puts("LOSE");return 0;
}

• inline
• block