1443: [JSOI2009]游戏Game - #include <Seter> - using namespace Orz;
1443: [JSOI2009]游戏Game
http://www.zybbs.org/JudgeOnline/problem.php?id=1443
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 144407 | Seter | 1443 | Accepted | 2340 kb | 448 ms | C/Edit | 2046 B | 2011-08-21 13:21:14 |
这题囧翻了，WA到实在受不了了去找Delostik神犇的代码然后几乎改得一模一样了还是WA。无奈下对拍，结果发现==比&先算……加个括号果断AC。不过时间只排了第十，第一的那个15MS怎么弄出来的……
做法很简单……黑白染色后构二分图然后判断没一个点是否必在最大匹配里……但是怎么输出WIN的位置想了好久，看了WJMZBMR神犇的题解也稀里糊涂，后来画了几张图看看好像又有点感觉了，再去看题解觉得好像是对的，看代码发现真的是对的……就是在残量网络上从S开始DFS一遍能DFS到的左边的点，和把边反向DFS一遍能DFS到的右边的点都是W位置。至于为什么是对的……呃……我反正证不出来，看看好象是对的就写了。我果然是苣蒻……
我想了一下，大致是这样的：假设用匈牙利算法，跑出来以后观察所有左边的点，不在最大匹配中的必定可以不在最大匹配中（废话
），对这些点继续DFS，所有能DFS到的左边的点必定可以通过这条DFS路增广使得这个点不在最大匹配中（已经是最大匹配了，如果能增广只可能将匹配数增加0）……右边也一样……但是由于构图原因所以右边的点DFS时需要把边反向（相当于反过来匈牙利一下）。
我的2B代码……（最近好像萌上了狂交……AC(5)都不罢休……我难道被Oleg带坏了么？）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #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;} |
By Seter
评论 (0)