CF1147F Zigzag Game（博弈+稳定婚姻）

木xx木大 · 2021-01-14 16:11:31 · 题解

CF1147F Zigzag Game

凡是牵扯到博弈近似物的题都好难啊！这题真是神仙题！（毕竟是CF 3500 的题啊）

前置知识：稳定婚姻问题

稳定婚姻问题是一种特殊的二分图匹配问题。其问题的一般表述形式为，有 n 男 n 女要结成伴侣，每名男性都按照其偏爱程度将所有女性排序，每名女性都按照其偏爱程度将所有男性排序。要求找到一个完美配对方案，使得配对方案是稳定的。其中一种配对方案是稳定的定义为，不存在两对伴侣 (a, b) 和 (c, d)，使得 a 更偏爱 d 而不是 b 且 d 更偏爱 a 而不是 c，即 w(a,d)>w(a,b) 且 w(d,a)>w(d,c)。

算法过程：

算法执行若干轮，每轮一名单身男性 x 向其最偏爱的没有表白过的女性 y。若 y 单身，则 x 和 y 结成伴侣；否则，若 y 比起当前伴侣更偏爱 x，则 y 抛弃当前伴侣选择 x；否则 x 表白失败。
若所有男性都有伴侣，则找到合法配对方案，退出算法。

本题solution

做过这题就知道，如果没有边权的限制，则原图必然存在完美匹配，B 必胜。因此我们不妨猜测在有了边权大小的限制之后仍然是 B 必胜，考虑 B 的必胜策略。

假设 A 选择 I（否则将边权取反即可），我们希望构造出一组匹配，使得对于任意两条匹配中的边 (a, b),(c,d) 满足：如果我方走完 (a,b) 后对方可以走 (b,c)，则我方可以接着走 (c, d)，即 w(b,c)>w(a,b) 且 w(b,c)>w(c,d)。换句话说，不能存在 w(a,b)<w(b,c)<w(c,d)。

如果令起点所在的一部（即 a,c 所在的一部）为按照边权升序排序，另一侧（即 b,d 所在的一部）按照边权降序排序，对于匹配关系 (a, b),(c,d) ，若 b 认为 c 比 a 优，则 c 不能认为 b 比 d 优，即若 w(b,a)<w(b,c) 则 w(c,d)<w(c,b) 。这实际上就是一个稳定婚姻问题，而稳定婚姻问题是必定有解的。按上面说的算法构造即可。

#include<bits/stdc++.h>
using namespace std;
namespace FGF
{
    int n,m;
    const int N=55;
    int a[N][N],rk[N][N],pos[N],nxt[N<<1];
    char s[5];
    vector<int> g[N],t;
    queue<int> q;
    void solve(int op)
    {
        memset(pos,0,sizeof(pos)),memset(nxt,0,sizeof(nxt));
        for(int i=1;i<=n;i++)
        {
            q.push(i);
            g[i].clear();
            for(int j=1;j<=n;j++)
                g[i].push_back(j);
            sort(g[i].begin(),g[i].end(),[&](int x,int y){return (a[i][x]<a[i][y])^op;});
        }
        for(int i=1;i<=n;i++)
        {
            t.clear();
            for(int j=1;j<=n;j++)
                t.push_back(j);
            sort(t.begin(),t.end(),[&](int x,int y){return (a[x][i]>a[y][i])^op;});
            for(int j=0;j<n;j++)
                rk[i][t[j]]=j+1;
        }
        while(q.size())
        {
            int u=q.front();
            q.pop();
            while(!nxt[u])
            {
                int v=g[u][pos[u]++];
                if(!nxt[v+n]||rk[v][nxt[v+n]]>rk[v][u])
                {
                    nxt[nxt[v+n]]=0;
                    if(nxt[v+n])q.push(nxt[v+n]);
                    nxt[v+n]=u,nxt[u]=v+n;
                }
            }
        }
    }
    void work()
    {
        cin>>m;
        while(m--)
        {
            cin>>n;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    scanf("%d",&a[i][j]);
            cout<<"B"<<endl; 
            cin>>s;
            if(s[0]=='D')
            {
                for(int i=1;i<=n;i++)
                    for(int j=1;j<=n;j++)
                        a[i][j]=-a[i][j];
            }
            int x;
            cin>>x;
            solve(x>n);
            cout<<nxt[x]<<endl; 
            cin>>x;
            while(~x)cout<<nxt[x]<<endl,cin>>x; 
        } 
    }
}
int main()
{
    FGF::work();
    return 0;
}