CF1147F Zigzag Game

Link
我们知道如果没有边权大小的限制那么一定先手必胜，因此我们不妨猜测在有了边权大小的限制之后仍然是先手必胜。
不失一般性，假设Alice选择I并将棋子放在某个左侧点。
我们任取一组最大匹配中的两条边\((u,v),(p,q)\)，那么我们希望构造出这样的情况：
若Alice将棋子从\(v\)移至\(p\)是合法的，那么Bob将棋子从\(p\)移到\(q\)也是合法的。
这样的话需要满足\(w(u,v),w(p,q)<w(v,p)\)。
我们称一组匹配是不好的当且仅当匹配中存在两条边\((u,v),(p,q)\)使得\(w(u,v)<w(v,p)<w(p,q)\)。
我们现在的任务是找到一组好的匹配。
这实际上就是一个稳定婚姻问题，令左侧点的偏好为按照边权生序排序，右侧点的偏好为按照边权降序排序即可。
稳定婚姻问题是有一个\(O(n^2)\)的解法的：
一个单身的男生向自己尚未表白的最喜欢的女生表白。
如果该女生现在没有男朋友，那么表白成功。
如果该女生已经有男朋友，并且更喜欢自己现在的男朋友，那么表白失败。
如果该女生已经有男朋友，并且更喜欢现在表白的这个男生，那么表白成功，之前的男朋友重新进入单身状态。

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
int read(){int x;scanf("%d",&x);return x;}
int n,e[51][51],rank[51][51],next[101],pos[51];
std::vector<int>vec[51],t;std::queue<int>q;
void work(int f)
{
    memset(pos+1,0,n<<2),memset(next+1,0,n<<3);
    for(int i=1,j;i<=n;++i) for(q.push(i),vec[i].clear(),j=1;j<=n;++j) vec[i].push_back(j);
    for(int i=1;i<=n;++i) std::sort(vec[i].begin(),vec[i].end(),[&](int a,int b){return (e[i][a]<e[i][b])^f;});
    for(int i=1;i<=n;++i)
    {
    t.clear();
    for(int j=1;j<=n;++j) t.push_back(j);
    std::sort(t.begin(),t.end(),[&](int a,int b){return (e[a][i]>e[b][i])^f;});
    for(int j=0;j<(int)t.size();++j) rank[i][t[j]]=j+1;
    }
    for(int u,v;!q.empty();)
    for(u=q.front(),q.pop();!next[u];)
    {
        v=vec[u][pos[u]++];
        if(!next[v+n]||rank[v][next[v+n]]>rank[v][u])
        {
        next[next[v+n]]=0;
        if(next[v+n]) q.push(next[v+n]);
        next[v+n]=u,next[u]=v+n;
        }
    }
}
int main()
{
    for(int t=read(),p;t;--t)
    {
    n=read();
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) e[i][j]=read();
    printf("B\n"),fflush(stdout);
    if(getchar(),getchar()=='D') for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) e[i][j]=-e[i][j];
    for(work((p=read())>n);~p;p=read()) printf("%d\n",next[p]),fflush(stdout);
    }
}

CF1147F Zigzag Game

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12304905.html