bzoj 1443: [JSOI2009]游戏Game 二分图博弈题意分析代码

96 阅读 0 评论 64 点赞

我是靠谱客的博主精明老虎，这篇文章主要介绍bzoj 1443: [JSOI2009]游戏Game 二分图博弈题意分析代码，现在分享给大家，希望可以做个参考。

题意

给出一个n*m的地图，有的格子不能走。先手可以选择某个格子开始，然后到后手走，再到先手走。每个格子只能走一次，不能走的那方算输。问对于哪些格子，先手有必胜策略。
n,m<=100

分析

首先考虑黑白染色，那么这就变成了一个二分图，然后求出这个二分图的最大匹配。
假设先手选择了一个非匹配点，那么后手就只能走匹配点，然后先手沿着匹配走。若某一次后手走到了一个非匹配点，那么就出现了一条增广路，与最大匹配矛盾，故先手必胜。
但是如果所有的点都最大匹配了呢？随便先手去选哪个点，后手都可以沿其匹配走，然后先手如果走，又是一个新的最大匹配中点，后手又走其匹配，然后后手就赢了。
那么我们就要考虑如何求出每个非匹配点。
跑一波网络流，我们dfs一遍，看从源点能到哪些染色时归到S集的点；
再dfs一遍，看从哪些染色时归到T集的点能到汇点。
这些点就是答案！（注意建边时需要为有向边！就是反向弧初始流量为0！）
为什么呢？
首先非匹配点肯定是会被扫到的，
然后是匹配点中的可行点：
我们将如何扫到这些可行点呢？
以S集点为例，我们会先扫到一个可行点，然后扫到一个T集点，然后再通过已经有流量的反向弧回到一个匹配点，这样这个匹配点就是可行的了！

代码

复制代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 105
#define inf 0x3f3f3f3f
using namespace std;

int n,m,cnt,s,t,dis[N*N],cur[N*N],last[N*N],map[N][N],ans,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},cho[N*N],flag,vis[N*N],bel[N*N];
char ch[N];
struct edge{int to,next,c;}e[N*N*10];
queue <int> q;

int point(int x,int y)
{
    return (x-1)*m+y;
}

void addedge(int u,int v,int c)
{
    e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt;
    e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt;
}

bool bfs()
{
    for (int i=s;i<=t;i++)
        dis[i]=0;
    dis[s]=1;
    while (!q.empty()) q.pop();
    q.push(s);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=last[u];i;i=e[i].next)
            if (e[i].c&&!dis[e[i].to])
            {
                dis[e[i].to]=dis[u]+1;
                if (e[i].to==t) return 1;
                q.push(e[i].to);
            }
    }
    return 0;
}

int dfs(int x,int maxf)
{
    if (x==t||!maxf) return maxf;
    int ret=0;
    for (int &i=cur[x];i;i=e[i].next)
        if (e[i].c&&dis[e[i].to]==dis[x]+1)
        {
            int f=dfs(e[i].to,min(e[i].c,maxf-ret));
            ret+=f;
            e[i].c-=f;
            e[i^1].c+=f;
            if (ret==maxf) break;
        }
    return ret;
}

void dinic()
{
    while (bfs())
    {
        for (int i=s;i<=t;i++)
            cur[i]=last[i];
        ans+=dfs(s,inf);
    }
}

void Dfs(int x,int d)
{
    vis[x]=1;
    if (bel[x]==d)
    {
        cho[x]=1;
        flag=1;
    }
    for (int i=last[x];i;i=e[i].next)
        if (!vis[e[i].to]&&e[i].c==d) Dfs(e[i].to,d);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for (int j=1;j<=m;j++)
            if (ch[j]=='#') map[i][j]=1;
    }
    cnt=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (i%2==j%2&&!map[i][j])
                for (int k=0;k<4;k++)
                {
                    int p=i+dx[k],q=j+dy[k];
                    if (p<1||p>n||q<1||q>m||map[p][q]) continue;
                    addedge(point(i,j),point(p,q),1);
                }
    s=0;t=n*m+1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (!map[i][j])
            {
                if (i%2==j%2) 
                {
                    addedge(s,point(i,j),1);
                    bel[point(i,j)]=1;
                }
                else addedge(point(i,j),t,1);
            }
    dinic();
    Dfs(s,1);
    memset(vis,0,sizeof(vis));
    Dfs(t,0);
    if (flag) printf("WINn");
    else printf("LOSEn");
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (cho[point(i,j)]) printf("%d %dn",i,j);
    return 0;
}

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 105
#define inf 0x3f3f3f3f
using namespace std;

int n,m,cnt,s,t,dis[N*N],cur[N*N],last[N*N],map[N][N],ans,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},cho[N*N],flag,vis[N*N],bel[N*N];
char ch[N];
struct edge{int to,next,c;}e[N*N*10];
queue <int> q;

int point(int x,int y)
{
    return (x-1)*m+y;
}

void addedge(int u,int v,int c)
{
    e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt;
    e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt;
}

bool bfs()
{
    for (int i=s;i<=t;i++)
        dis[i]=0;
    dis[s]=1;
    while (!q.empty()) q.pop();
    q.push(s);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=last[u];i;i=e[i].next)
            if (e[i].c&&!dis[e[i].to])
            {
                dis[e[i].to]=dis[u]+1;
                if (e[i].to==t) return 1;
                q.push(e[i].to);
            }
    }
    return 0;
}

int dfs(int x,int maxf)
{
    if (x==t||!maxf) return maxf;
    int ret=0;
    for (int &i=cur[x];i;i=e[i].next)
        if (e[i].c&&dis[e[i].to]==dis[x]+1)
        {
            int f=dfs(e[i].to,min(e[i].c,maxf-ret));
            ret+=f;
            e[i].c-=f;
            e[i^1].c+=f;
            if (ret==maxf) break;
        }
    return ret;
}

void dinic()
{
    while (bfs())
    {
        for (int i=s;i<=t;i++)
            cur[i]=last[i];
        ans+=dfs(s,inf);
    }
}

void Dfs(int x,int d)
{
    vis[x]=1;
    if (bel[x]==d)
    {
        cho[x]=1;
        flag=1;
    }
    for (int i=last[x];i;i=e[i].next)
        if (!vis[e[i].to]&&e[i].c==d) Dfs(e[i].to,d);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for (int j=1;j<=m;j++)
            if (ch[j]=='#') map[i][j]=1;
    }
    cnt=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (i%2==j%2&&!map[i][j])
                for (int k=0;k<4;k++)
                {
                    int p=i+dx[k],q=j+dy[k];
                    if (p<1||p>n||q<1||q>m||map[p][q]) continue;
                    addedge(point(i,j),point(p,q),1);
                }
    s=0;t=n*m+1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (!map[i][j])
            {
                if (i%2==j%2) 
                {
                    addedge(s,point(i,j),1);
                    bel[point(i,j)]=1;
                }
                else addedge(point(i,j),t,1);
            }
    dinic();
    Dfs(s,1);
    memset(vis,0,sizeof(vis));
    Dfs(t,0);
    if (flag) printf("WINn");
    else printf("LOSEn");
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (cho[point(i,j)]) printf("%d %dn",i,j);
    return 0;
}