二分图博弈学习笔记

2024-01-24 13:34:37

二分图博弈是博弈的一种，如今拿出来讲一下。

二分图博弈问题都具有一下特征：

  • 有向图上所有点可以分为两个点集，点集内部没有连边。
  • 每一次的决策都是把一个点移动到另一个点，不能重复经过一个点，不能移动就判负。

定理：

如果起始点一定是 任何 最大匹配中的点，那么从这个点开始，先手必胜，否则先手必输。

  • 证明：
  • 首先考虑这个点不满足以上条件，则其不管走到哪个点，这个点一定是匹配点，否则不满足是最大匹配的性质，然后后手就可以沿匹配边走。然后先手依然只能走到匹配点，否则就存在增广路，然后后手再走。因为是最大匹配，所以最后一定是先手无路可走，因为如果是后手无路可走的话，就会存在增广路。
  • 由以上证明同样可以得到，先手必胜的充要条件是满足定理条件。

应用

我们考虑如何来解题。以下我们皆用匈牙利算法来求解二分图最大匹配，如果对复杂度有要求可以用 dinic，我们只需要利用匹配结果或跑完网络流之后的残余网络。

我们先跑一遍匈牙利，求出一组可行解。

然后我们从所有没有被遍历的点开始，首先这些点一定是先手必败的，从这些点开始，看能通过 非匹配边-匹配边-非匹配边-匹配边 的方式走到哪些点， 凡是经过的点都是必败态。这个过程我们需要防止重复遍历，那么整个算法的时间复杂度瓶颈实际上是在求解二分图最大匹配上，难度是建图难度。

如果是跑网络流的话，实际上应该是在残余网络上从源点沿着流量为 \(1\) 走，从汇点沿着流量为 \(0\) 的边走即可，然后分别经过的左部点或右部点都设置为 \(0\)。之所以这样做是因为要保证我们遍历的边是 非匹配边-匹配边-非匹配边-匹配边。

如果是跑网络流的话还需要注意一个点，就是源点只能否定左部点，汇点只能否定右部点，我们在遍历的时候需要记录当前是左部点还是右部点。

例题

T1

链接

我们考虑这就是一个二分图匹配，按照上面所说，直接做即可。注意，因为起点只能放在山峰，所以我们可以只遍历一边而不用遍历山谷的点。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 10010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> inline T Min(T a,T b){return a<b?a:b;}

struct edge{
    int to,next;
    inline void Init(int to_,int ne_){
        to=to_;next=ne_;
    }
}li[N<<1];
int head[N],tail;

inline void Add(int from,int to){
    li[++tail].Init(to,head[from]);
    head[from]=tail;
}

int n,m,Match[N];
bool vis[N];

inline bool dfs(int k){
    for(int x=head[k];x;x=li[x].next){
        int to=li[x].to;
        if(!vis[to]){
            vis[to]=1;
            if(!Match[to]||dfs(Match[to])){
                Match[to]=k;return 1;
            }
        }
    }
    return 0;
}

inline void Init(){
    read(n);read(m);
    for(int i=1;i<=m;i++){
        int from,to;read(from);read(to);to+=n;
        Add(from,to);Add(to,from);
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        if(dfs(i)) tot++;
        memset(vis,0,sizeof(vis));
    }
    // printf("tot=%d\n",tot);
}

bool Ans[N],Not[N];

inline void Dfs(int k){
    vis[k]=1;
    for(int x=head[k];x;x=li[x].next){
        int to=li[x].to;
        if(vis[Match[to]]) continue;
        Ans[Match[to]]=0;Dfs(Match[to]);
    }
}

inline void Solve(){
    for(int i=1;i<=n;i++) Ans[i]=1;
    for(int i=1;i<=(n<<1);i++) vis[i]=0;
    for(int i=n+1;i<=(n<<1);i++) Not[Match[i]]=1;
    // for(int i=n+1;i<=(n<<1);i++){
    //     printf("%d %d\n",i,Match[i]);
    // }
    for(int i=1;i<=n;i++) if(!Not[i]) Ans[i]=0;
    for(int i=1;i<=n;i++){
        if(Not[i]) continue;
        if(vis[i]) continue;
        Dfs(i);
    }
}

inline void Print(){
    for(int i=1;i<=n;i++){
        if(Ans[i]) puts("Slavko");
        else puts("Mirko");
    }
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    Init();Solve();Print();
    return 0;
}

T2

链接

我们考虑这个棋盘其实也是一个二分图，不难发现存在一种染色方式使得一个格点的相邻格点与自身都不是同一种颜色，然后我们考虑直接建二分图，跑即可。这个题注意要左右两边都要遍历。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 110
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

struct edge{
    int from,to,next;
    inline void Init(int fr_,int to_,int ne_){
        from=fr_;to=to_;next=ne_;
    }
}li[(N*N)<<2];
int head[N*N],tail;

inline void Add(int from,int to){
    li[++tail].Init(from,to,head[from]);
    head[from]=tail;
}

int n,m;
char a[N][N];
inline char GetChar(){
    char c=getchar();
    while(c!='#'&&c!='.'){
        c=getchar();
    }
    return c;
}

const int fx[]={0,0,0,1,-1};
const int fy[]={0,1,-1,0,0};
vector<int> L,R;

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

inline pair<int,int> PID(int x){
    int a=x/m+1,b=x%m;
    if(b==0){a--;b+=m;}
    return make_pair(a,b);
}

inline void Init(){
    read(n);read(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=GetChar();
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(a[i][j]=='#') continue;
            if((i+j)&1) R.push_back(ID(i,j));
            else L.push_back(ID(i,j));
            for(int k=1;k<=4;k++){
                int dx=i+fx[k],dy=j+fy[k];
                if(a[dx][dy]=='#'||dx>n||dy>m||dx<=0||dy<=0) continue;
                Add(ID(i,j),ID(dx,dy));
                // printf("Add edge: %d %d\n",ID(i,j),ID(dx,dy));
            }
        }
    // puts("L");
    // for(int i:L) printf("%d ",i);
    // puts("\nR");
    // for(int i:R) printf("%d ",i);puts("");
}

int Match[N*N];
bool vis[N*N],Not[N*N],Ans[N*N];

inline bool dfs(int k){
    for(int x=head[k];x;x=li[x].next){
        int to=li[x].to;
        if(!vis[to]){
            vis[to]=1;
            if(!Match[to]||dfs(Match[to])){
                Match[to]=k;Match[k]=to;
                return 1;
            }
        }
    }
    return 0;
}

inline void Dfs(int k){
    vis[k]=1;
    for(int x=head[k];x;x=li[x].next){
        int to=li[x].to;
        if(vis[Match[to]]) continue;
        Ans[Match[to]]=0;Dfs(Match[to]);
    }
}

vector<int> ans;

inline void Solve(){
    for(int i:L){
        dfs(i);
        memset(vis,0,sizeof(vis));
    }
    // puts("Match");
    // for(int i:R){
    //     printf("Match[%d]=%d\n",i,Match[i]);
    // }
    // for(int i:L){
    //     printf("Match[%d]=%d\n",i,Match[i]);
    // }
    for(int i:R){
        if(!Match[i]) continue;
        Not[Match[i]]=1;Not[i]=1;
    }
    memset(Ans,1,sizeof(Ans));
    for(int i:L){if(!Not[i]) Ans[i]=0;}
    for(int i:R){if(!Not[i]) Ans[i]=0;}
    for(int i:L){
        if(Not[i]) continue;
        if(vis[i]) continue;
        Dfs(i);
    }
    for(int i:R){
        if(Not[i]) continue;
        if(vis[i]) continue;
        Dfs(i);
    }
    // for(int i:L) printf("Ans[%d]=%d\n",i,Ans[i]);
    // for(int i:R) printf("Ans[%d]=%d\n",i,Ans[i]);
    bool op=0;
    for(int i:L){
        if(!Ans[i]){op=1;break;}
    }
    for(int i:R){
        if(!Ans[i]){op=1;break;}
    }
    if(!op){puts("LOSE");exit(0);}
    if(op){
        puts("WIN");
        for(int i:L){
            if(!Ans[i]) ans.push_back(i);
        }
        for(int i:R){
            if(!Ans[i]) ans.push_back(i);
        }
        sort(ans.begin(),ans.end());
        for(int i:ans){
            printf("%d %d\n",PID(i).first,PID(i).second);
        }
        return;
    }
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    Init();Solve();
    return 0;
}

好久不写匈牙利，竟然写错了两个地方：

  1. vis 数组没有清空
  2. dfs(Match[to]) 写成 dfs(to)。

T3

这个题的链接在正睿上，大部分人并没有权限观看。

链接

首先考虑一个马的时候，不难发现马移动一步的话，坐标之和的奇偶性发生变化，于是我们可以根据坐标和的奇偶性来把点分成两个集合。跑二分图博弈就可以。

这个题我是建图用网络流跑的，细节具体看代码。

如果是两个马，我们需要考虑如何建图，不难发现我们二分图中的一个节点代表的是两匹马的坐标，注意到以上性质仍然成立，所以我们可以给所有合法点对进行标号，建边即可。

注意这里一开始忘记枚举另一点的边，再者一定要想清楚再开始写，不然十分容易写错。还要注意的值两匹马本质相同，所以建边细节较多，具体看代码。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 16
#define M N*N*N*N
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> inline T Min(T a,T b){return a<b?a:b;}

struct edge{
    int to,next,f;
    inline void Init(int to_,int ne_,int f_){
        to=to_;next=ne_;f=f_;
    }
}li[M*16];
int head[M],tail=1,now[M];

inline void Add(int from,int to){
    li[++tail].Init(to,head[from],1);
    head[from]=tail;swap(from,to);
    li[++tail].Init(to,head[from],0);
    head[from]=tail;
}

bool sol[N][N];
int n,m,k,s,t;

const int fx[]={0,-2,-1,1,2,2,1,-1,-2};
const int fy[]={0,1,2,2,1,-1,-2,-2,-1};

inline void Init(){
    read(n);read(m);read(k);
    for(int i=1;i<=k;i++){
        int a,b;read(a);read(b);
        sol[a][b]=1;
    }
}

namespace Work1{
    inline int ID(int x,int y){
        return (x-1)*n+y;
    }

    inline pair<int,int> PID(int x){
        int a=x/n+1,b=x%n;
        if(b==0){a--;b+=n;}
        return make_pair(a,b);
    }

    vector<int> L,R;

    inline void Build(){
        s=n*n+1;t=n*n+2;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(sol[i][j]) continue;
                if((i+j)&1) R.push_back(ID(i,j));
                else L.push_back(ID(i,j));
                if((i+j)&1) continue;
                for(int k=1;k<=8;k++){
                    int dx=i+fx[k],dy=j+fy[k];
                    if(sol[dx][dy]||dx<=0||dy<=0||dx>n||dy>n) continue;
                    Add(ID(i,j),ID(dx,dy));
                    // printf("Add edge %d %d\n",ID(i,j),ID(dx,dy));
                }
            }
        }
        for(int i:L) Add(s,i);
        for(int i:R) Add(i,t);
        // printf("Compelete Initing\n");
        // puts("L:");
        // for(int i:L) printf("%d ",i);
        // puts("\nR:");
        // for(int i:R) printf("%d ",i);puts("");
    }

    int d[M];
    queue<int> q;
    inline bool bfs(){
        // printf("here\n");
        memset(d,0,sizeof(d));
        while(q.size()) q.pop();
        q.push(s);d[s]=1;now[s]=head[s];
        while(q.size()){
            int top=q.front();q.pop();
            for(int x=head[top];x;x=li[x].next){
                int to=li[x].to,f=li[x].f;
                if(d[to]||!f) continue;
                q.push(to);d[to]=d[top]+1;
                now[to]=head[to];if(to==t) return 1;
            }
        }
        return d[t];
    }

    inline int dinic(int k,int flow){
        if(k==t) return flow;
        int rest=flow,x;
        for(x=now[k];x&&rest;x=li[x].next){
            int to=li[x].to,f=li[x].f;
            if(d[to]!=d[k]+1||!f) continue;
            int val=dinic(to,Min(flow,f));
            if(!val) d[to]=0;
            li[x].f-=val;li[x^1].f+=val;rest-=val;
        }
        now[k]=x;return flow-rest;
    }

    bool Ans[M],vis[M];

    inline void dfs(int k,int c,int now){
        vis[k]=1;
        if(now==c) Ans[k]=0;
        for(int x=head[k];x;x=li[x].next){
            int to=li[x].to,f=li[x].f;
            if(f!=c||vis[to]) continue;
            dfs(to,c,now^1);
        }
    }

    inline void Solve(){
        int ans=0;
        while(bfs()) ans+=dinic(s,INF);
        // printf("ans=%d\n",ans);
        for(int i:L) Ans[i]=1;
        for(int i:R) Ans[i]=1;
        // printf("Ans[1]=%d\n",Ans[1]);
        dfs(s,1,0);memset(vis,0,sizeof(vis));
        dfs(t,0,1);
        int res=0;
        for(int i=1;i<=n*n;i++) if(Ans[i]) res++;
        printf("%d\n",res);
    }
};

namespace Work2{

    vector<int> L,R;
    int id[N][N][N][N],tot;
    
    inline void Trans(int &a,int &b,int &c,int &d){
        if(make_pair(a,b)>make_pair(c,d)){swap(a,c);swap(b,d);}
    }

    inline void Build(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(sol[i][j]) continue;
                for(int k=1;k<=n;k++)
                    for(int l=1;l<=n;l++){
                        if(sol[k][l]) continue;
                        if(make_pair(i,j)>=make_pair(k,l)) continue;
                        id[i][j][k][l]=++tot;
                        // printf("id[%d][%d][%d][%d]=%d\n",i,j,k,l,id[i][j][k][l]);
                        if((i+j+k+l)&1) R.push_back(tot);
                        else L.push_back(tot);
                    }
            }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(sol[i][j]) continue;
                for(int k=1;k<=n;k++){
                    for(int l=1;l<=n;l++){
                        if(sol[k][l]) continue;
                        if(make_pair(i,j)>=make_pair(k,l)) continue;
                        if((i+j+k+l)&1) continue;
                        for(int q=1;q<=8;q++){
                            int x=k,y=l;
                            int dx=i+fx[q],dy=j+fy[q];
                            if(sol[dx][dy]||(dx==x&&dy==y)||dx<=0||dy<=0||dx>n||dy>n) continue;
                            Trans(x,y,dx,dy);
                            Add(id[i][j][k][l],id[x][y][dx][dy]);
                            // printf("%d %d\n",id[i][j][k][l],id[x][y][dx][dy]);
                        }
                        for(int q=1;q<=8;q++){
                            int x=i,y=j;
                            int dx=k+fx[q],dy=l+fy[q];
                            if(sol[dx][dy]||(dx==x&&dy==y)||dx<=0||dy<=0||dx>n||dy>n) continue;
                            Trans(x,y,dx,dy);
                            Add(id[i][j][k][l],id[x][y][dx][dy]);
                            // printf("%d %d\n",id[i][j][k][l],id[x][y][dx][dy]);
                        }
                    }
                }
            }
        }
        s=++tot;t=++tot;
        for(int i:L) Add(s,i);
        for(int i:R) Add(i,t);
        // puts("L:");for(int i:L) printf("%d ",i);printf("\nsize=%d",L.size());
        // puts("\nR:");for(int i:R) printf("%d ",i);printf("\nsize=%d\n",R.size());
    }

    int d[M];
    queue<int> q;
    inline bool bfs(){
        // printf("here\n");
        memset(d,0,sizeof(d));
        while(q.size()) q.pop();
        q.push(s);d[s]=1;now[s]=head[s];
        while(q.size()){
            int top=q.front();q.pop();
            for(int x=head[top];x;x=li[x].next){
                int to=li[x].to,f=li[x].f;
                if(d[to]||!f) continue;
                q.push(to);d[to]=d[top]+1;
                now[to]=head[to];if(to==t) return 1;
            }
        }
        return d[t];
    }

    inline int dinic(int k,int flow){
        if(k==t) return flow;
        int rest=flow,x;
        for(x=now[k];x&&rest;x=li[x].next){
            int to=li[x].to,f=li[x].f;
            if(d[to]!=d[k]+1||!f) continue;
            int val=dinic(to,Min(flow,f));
            if(!val) d[to]=0;
            li[x].f-=val;li[x^1].f+=val;rest-=val;
        }
        now[k]=x;return flow-rest;
    }

    bool Ans[M],vis[M];

    inline void dfs(int k,int c,int now){
        vis[k]=1;
        if(now==c) Ans[k]=0;
        for(int x=head[k];x;x=li[x].next){
            int to=li[x].to,f=li[x].f;
            if(f!=c||vis[to]) continue;
            dfs(to,c,now^1);
        }
    }

    inline void Solve(){
        int ans=0;
        while(bfs()) ans+=dinic(s,INF);
        // printf("ans=%d\n",ans);
        for(int i:L) Ans[i]=1;
        for(int i:R) Ans[i]=1;
        // printf("Ans[1]=%d\n",Ans[1]);
        dfs(s,1,0);memset(vis,0,sizeof(vis));
        dfs(t,0,1);
        int res=0;
        for(int i=1;i<=tot;i++) if(Ans[i]) res++;
        printf("%d\n",res);
    }
};

inline void Solve(){
    if(m==1){
        Work1::Build();Work1::Solve();
    }
    else{
        Work2::Build();Work2::Solve();
    }
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    Init();Solve();
    return 0;
}
上一篇：P1220 关路灯


下一篇：样式代码