Zigzag Game

题解

对于原边权需要的上升与下降我们可以通过翻转边权来进行处理，下面不妨设我们需要边权递增。
如果我们才走了$(a,b)$，如果对于任意的$c$存在唯一的$d$使得$w(c,d)>w(b,c)\wedge w(a,b)>w(b,c)$，那么我们显然可以得到一种走法，我们从$a$走到$b$，对方无论走到哪个$c$，我们都可以走到一个未走到的$d$，这样胜利的显然是我们了。
上面的做法显然需要我们迈出第一步，也就是我们得是后手。
但怎么对所有的找到匹配点呢？
显然，如果我们的出发点$⩽n$的话，$⩽n$的点肯定会尽可能去匹配较大的边，而$>n$的点就是与$⩽n$反着来的，尽可能去匹配较小的边。
对于$⩽n$的点，它们的对象越大，就越能让自己递增，而$>n$的对象匹配的边越小，就越能让对方走回去的选择越少，越不可能超过我们下一次走的边。

这个匹配的过程也就是我们的 稳定婚姻问题。
就是给出$n$个训狗师与$n$条 JZM，每个训狗师对每条JZM有一个满意度，每条JZM对每个训狗师也有一个满意度。
就是给出$n$个男性和$n$个女性，每个男/女性对每个女/男性有一个满意度。
要求你将这$n$对人和JZM男女匹配，最后不存在一未对男女，对对方都比自己的伴侣更加满意。
在1962年美国数学家 David Gale 和 Lloyd Shapley 就提出了一种对该问题解决方法。
我们可以让男性去匹配女性，让男性从自己最喜欢的女性匹配起，如果该男性成为了匹配到该女性的该女性最喜欢的男性，那就让他与这个女性匹配，否则让这个男性匹配他喜欢的下一个女性。
实际实现过程可以记录一下哪些男性还未匹配女性，将其放入队列中，对于队首找到它下一个能匹配的女性，如果他比这个女性匹配的男性的优，就用他把那个男性替换掉，放入队列。
容易证明，最后一定能够成功匹配。
PS:感觉这种说法很容易被女拳冲的样子，但事实上男女是等价的。

显然，我们可以用上面的方法解决我们的问题。
我们将左部点与右部点进行匹配，设左部点对右部点的权值$a_{i,j}{w}_{i,j}$，右部点对左部点的权值为$b_{j,i}=-w_{j,i}$。
可以证明不存在上面的点对$(a,b),(c,d)$会产生矛盾，
用反证法，如果产生矛盾，那么有$w_{a,b}>w_{b,c}>w_{c,d}$,$a_{c,b}>a_{c,d},b_{b,c}>b_{b,a}$显然出现了相好的男女为被匹配的情况，与我们的匹配结果矛盾。
所以可以证明我们只要像稳定婚姻问题一样就可以求解这道题了。
我们将所有匹配算出来后像我们上面那样写的走就行了。

由于要先排序，所以时间复杂度是$O\left(n^2\log n\right)$的。
但实际上这道题可以桶排，所以是$O\left(n^2\right)$。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 405
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;       
const int INF=0x3f3f3f3f;       
const int mo=1e9+7;
const int inv2=499122177;
const int jzm=2333;
const int zero=10000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<LL,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int t,n,mp[55][55],p[105],ord[55][55],id[55],nowid;
queue<int>q;
bool cmp(int x,int y){return mp[nowid][x]>mp[nowid][y];}
signed main(){read(t);while(t--){read(n);int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)read(mp[i][j]);puts("B");fflush(stdout);char opt[5]={};int now;scanf("\n%s %d",opt+1,&now);if((opt[1]=='I')^(now>n))for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)mp[i][j]*=-1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)ord[i][j]=j;nowid=i;sort(ord[i]+1,ord[i]+n+1,cmp);}for(int i=1;i<=n;i++)q.push(i),id[i]=1,p[i]=0;while(!q.empty()){int u=q.front();q.pop();while(id[u]<=n){int v=ord[u][id[u]];if(!p[v]||mp[u][v]<mp[p[v]][v]){if(p[v])q.push(p[v]);p[v]=u;break;}id[u]++;}}for(int i=1;i<=n;i++)p[i+n]=p[i];for(int i=1;i<=n;i++)p[p[i+n]]=i+n;printf("%d\n",p[now]);fflush(stdout);while(1){read(now);if(now<0)break;printf("%d\n",p[now]);fflush(stdout);}assert(now!=-2);}return 0;
}

谢谢！！！