tofacebook.com -专业IT技术社区(贪吃蛇学院) BZOJ1443: [JSOI2009]游戏Game Web程序 - 贪吃蛇学院-专业IT技术平台
142°

BZOJ1443: [JSOI2009]游戏Game Web程序

标签:eof   code   div   turn   com   上下左右   开始   continue   另一个   

$n \leq 100$,$m \leq 100$的$n*m$地图,现进行一个博弈:后手先选个点放棋子,然后先后手轮流向上下左右某个方向移动棋子一步,不能移到障碍点,一个非障碍点不能走两次。问所有后手能赢的位置。

可以发现网格图是一个二分图,在移动时好像在二分图的两边反复横跳。可以在二分图这个模型上进行尝试,比如说,求最大匹配,看一下匹配点和非匹配点的情况。

从匹配点开始:(不如把放棋子那人叫B)

A如果走了一条匹配边,那B可以随意走一步,这一步一定是非匹配边,然后轮到A:1、如果A又走了一条匹配边,回到刚才情况;2、A没走匹配边,那情况就反转了,因为连走两条非匹配边一定会走到一个匹配点。等等蛤,B为啥一定可以随意走一步?陷入江局。。

从非匹配点开始:

A会走一条非匹配边到一个匹配点,然后B只要走最大匹配即可,因为A每一步都只能走非匹配边到另一个匹配点(如果不是匹配点,那他们走过的路就可以增广,不符合最大匹配)。这样A输定。

也就是说,只要选择不出现在某一个最大匹配的点,就一定赢。

直接一次最大匹配算法只能求一个最大匹配,没匹配的点一定是答案。但是,只要在最大匹配算法结束后,从S集的点沿着非匹配边-匹配边走到另外的S集点,这些“另外的点”也是答案,因为走过的路径相当于做了一次没损失没收益的增广,依然是最大匹配。同理,T集的点沿着非匹配边-匹配边走到的T集点也是答案。

我用的Dinic求最大匹配,所以就看S能到达哪些S集点以及哪些T集点能到T即可。

技术分享图片
  1 //#include<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 //#include<queue>
  6 //#include<time.h>
  7 //#include<complex>
  8 #include<algorithm>
  9 #include<stdlib.h>
 10 using namespace std;
 11 
 12 int n,m;
 13 #define maxn 10011
 14 #define maxm 100011
 15 
 16 bool vis[111][111]; int col[maxn],id[111][111],tot;
 17 int qx[maxn],qy[maxn],head,tail;
 18 const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
 19 bool mp[111][111]; char s[111];
 20 void bfs(int sx,int sy)
 21 {
 22     head=0; tail=1; qx[0]=sx; qy[0]=sy;
 23     col[id[sx][sy]]=1; vis[sx][sy]=1;
 24     while (head!=tail)
 25     {
 26         int nx=qx[head],ny=qy[head]; head++;
 27         for (int i=0;i<4;i++)
 28         {
 29             int xx=nx+dx[i],yy=ny+dy[i];
 30             if (xx<1 || xx>n || yy<1 || yy>m || !mp[xx][yy] || vis[xx][yy]) continue;
 31             vis[xx][yy]=1; col[id[xx][yy]]=-col[id[nx][ny]];
 32             qx[tail]=xx; qy[tail]=yy; tail++;
 33         }
 34     }
 35 }
 36 
 37 struct Edge{int from,to,cap,flow,next;};
 38 struct Network
 39 {
 40     Edge edge[maxm]; int first[maxn],le,n;
 41     Network() {le=2;}
 42     void in(int x,int y,int cap) {Edge &e=edge[le]; e.from=x; e.to=y; e.cap=cap; e.flow=0; e.next=first[x]; first[x]=le++;}
 43     void insert(int x,int y,int cap) {in(x,y,cap); in(y,x,0);}
 44     int dis[maxn],s,t,que[maxn],head,tail,cur[maxn];
 45     bool bfs()
 46     {
 47         for (int i=1;i<=n;i++) dis[i]=0x3f3f3f3f; dis[s]=0;
 48         head=0; tail=1; que[0]=s;
 49         while (head!=tail)
 50         {
 51             int now=que[head++];
 52             for (int i=first[now];i;i=edge[i].next)
 53             {
 54                 Edge &e=edge[i];
 55                 if (e.cap>e.flow && dis[e.to]==0x3f3f3f3f)
 56                 {
 57                     dis[e.to]=dis[now]+1;
 58                     que[tail++]=e.to;
 59                 }
 60             }
 61         }
 62         return dis[t]!=0x3f3f3f3f;
 63     }
 64     int dfs(int x,int a)
 65     {
 66         if (x==t || !a) return a;
 67         int flow=0,f;
 68         for (int &i=cur[x];i;i=edge[i].next)
 69         {
 70             Edge &e=edge[i];
 71             if (dis[e.to]==dis[x]+1 && (f=dfs(e.to,min(a,e.cap-e.flow)))>0)
 72             {
 73                 flow+=f; e.flow+=f;
 74                 edge[i^1].flow-=f; a-=f;
 75                 if (!a) return flow;
 76             }
 77         }
 78         return flow;
 79     }
 80     int Dinic(int s,int t)
 81     {
 82         this->s=s; this->t=t;
 83         int ans=0;
 84         while (bfs())
 85         {
 86             for (int i=1;i<=n;i++) cur[i]=first[i];
 87             ans+=dfs(s,0x3f3f3f3f);
 88         }
 89         return ans;
 90     }
 91     bool vis[maxn],v2[maxn];
 92     void solve()
 93     {
 94         head=0; tail=1; que[0]=s;
 95         memset(v2,0,sizeof(v2)); v2[s]=1;
 96         while (head!=tail)
 97         {
 98             int now=que[head++]; if (col[now]==1) vis[now]=1;
 99             for (int i=first[now];i;i=edge[i].next)
100             {
101                 Edge &e=edge[i]; if (v2[e.to] || e.to==t || e.cap<=e.flow) continue;
102                 que[tail++]=e.to,v2[e.to]=1;
103             }
104         }
105         head=0; tail=1; que[0]=t;
106         memset(v2,0,sizeof(v2)); v2[t]=1;
107         while (head!=tail)
108         {
109             int now=que[head++]; if (col[now]==-1) vis[now]=1;
110             for (int i=first[now];i;i=edge[i].next)
111             {
112                 Edge &e=edge[i]; if (v2[e.to] || e.to==s) continue;
113                 if (e.cap==e.flow) que[tail++]=e.to,v2[e.to]=1;
114             }
115         }
116     }
117 }g;
118 
119 int main()
120 {
121     scanf("%d%d",&n,&m);
122     for (int i=1;i<=n;i++)
123     {
124         scanf("%s",s+1);
125         for (int j=1;j<=m;j++) mp[i][j]=(s[j]==.);
126     }
127     for (int i=1;i<=n;i++)
128         for (int j=1;j<=m;j++) if (mp[i][j])
129             id[i][j]=++tot;
130     for (int i=1;i<=n;i++)
131         for (int j=1;j<=m;j++)
132             if (mp[i][j] && !vis[i][j]) bfs(i,j);
133     int s=tot+1,t=s+1; g.n=t;
134     for (int i=1;i<=n;i++)
135         for (int j=1;j<=m;j++) if (mp[i][j])
136             for (int k=0;k<4;k+=2)
137             {
138                 int xx=i+dx[k],yy=j+dy[k];
139                 if (xx<1 || xx>n || yy<1 || yy>m || mp[xx][yy]==0) continue;
140                 if (col[id[i][j]]==1) g.insert(id[i][j],id[xx][yy],1);
141                 else g.insert(id[xx][yy],id[i][j],1);
142             }
143     for (int i=1;i<=n;i++)
144         for (int j=1;j<=m;j++) if (mp[i][j])
145         {
146             if (col[id[i][j]]==1) g.insert(s,id[i][j],1);
147             else g.insert(id[i][j],t,1);
148         }
149     g.Dinic(s,t);
150     g.solve();
151     bool flag=0;
152     for (int i=1;i<=n;i++)
153         for (int j=1;j<=m;j++)
154             if (g.vis[id[i][j]])
155             {
156                 if (!flag) {flag=1; puts("WIN");}
157                 printf("%d %d\n",i,j);
158             }
159     if (!flag) puts("LOSE");
160     return 0;
161 }
View Code

 

BZOJ1443: [JSOI2009]游戏Game

标签:eof   code   div   turn   com   上下左右   开始   continue   另一个   

原文地址:https://www.cnblogs.com/Blue233333/p/8570449.html


本文由百家号/熊掌号作者上传并发布,百家号仅提供信息发布平台。文章仅代表作者个人观点,不代表百度立场。

已有 0 条评论

    我有话说: