金条争夺 题解
Part 0 题意理解
首先容易发现最多只会发生一次抢夺，因为假如 A 抢了之后又会被 B 抢回去，那么 A 肯定不会去抢，因为所有人都希望不要遗憾离场，而所有人又足够聪明。所以我们先解决会不会发生抢夺的问题。
什么时候会发生抢夺呢？显然，是抢了之后不会被抢回去时。假如我们把所有能发生抢夺（即没有私交，又不在同一组）的人之间连一条边，容易发现这其实是个二分图博弈模型（其实因为我没学过所以并不容易 awa），金条仅能按边移动。
假如最后金条不能移动时不在 $P$ 组（即模型中“先手胜”的情况，为方便叙述设这组为 $Q$），那么可以发生抢夺，因为假如 $Q$ 组的 $A$ 抢了后被 $P$ 组的 $B$ 抢回去，那 $Q$ 组就必定有一个 $C$ 能抢回去，$B$ 就不会去抢。同理，假如最后金条留在 $P$ 组（即“后手胜”），那么就不会发生抢夺。
Part 1 二分图博弈
由于我之前没学过二分图博弈模型所以我这里要讲一讲（方便理解）。
首先，这个模型是有一个二分图，其中起点 $H$ 上有一个棋子，先手后手分别沿边移动棋子，不能重复经过某个点，最后无路可走的就输了。
这个模型的结论如下：
假如二分图最大匹配一定包含起点 $H$，先手必胜；反之，先手必败。
假如二分图最大匹配一定包含 $H$，那么先手只需要按某条匹配边移动棋子，后手无论如何必定会沿一条非匹配边移到另一个匹配点上（或者无路可走），所以先手只需要每次沿匹配边走即可。证明的话，设路径为 $H \to P_1 \to P_2\to P_3\dots$，当前在 $P_i$，下一步后手会沿边 $P_i-P_{i+1}$ 移动。由于 $P_{i-1}-P_i$ 是一条匹配边，所以 $P_i-P_{i+1}$ 必定是一条非匹配边。假如 $P_{i+1}$ 不是匹配点，那么存在一个大小和原匹配 ${H-P_1,P_2-P_3\dots P_{i-1}-P_i}$ 相等的匹配 ${P_1-P_2,P_3-P_4\dots P_i-P_{i+1}}$，与最大匹配一定包含 $H$ 矛盾。
假如二分图最大匹配不一定包含 $H$，那么必定存在一个最大匹配 $M$ 不包含 $H$，先手第一步必定会走到 $M$ 的匹配点上。假如第一步不移动到匹配点上，那么 $H-P_1$ 就可以和 $M$ 匹配，与 $M$ 是最大匹配矛盾。往后每一步先手都必定走到另一个匹配点上，后手只要沿 $M$ 的匹配边走即可，同样设路径为 $H \to P_1 \to P_2\to P_3\dots$，那么 $M$ 即为 ${P_1-P_2,P_3-P_4\dots,P_{i-1}-P_i}$，假如 $P_{i+1}$ 不是匹配点，那么存在另一个更大的匹配 ${H-P_1,P_2-P_3\dots P_i-P_{i+1}}$，同样与 $M$ 为最大匹配矛盾。
回到这道题，假如 $P=2$，我们就可以把两组的信息交换一下（用数学语言就是“不妨设 $P=1$”，最后输出时注意一下即可），将第一组人设为 $1\sim n$，第二组为 $n+1\sim n+m$，将所有不在同一组也没有私交的人两两连边组成二分图，先去掉点 $X$ 跑一遍最大匹配，再加上它跑一遍最大匹配，假如加上后最大匹配变大了那么说明所有最大匹配都包含点 $X$，即先手胜，反之后手胜（可以直接输出初始情况）。这一步的复杂度为 $O((n+m)\sqrt{nm-k})$（好怪的复杂度）。
Part 2 判断可行边
假如先手胜，那么我们还要解决另一个问题：谁会抢金条。
容易发现，会抢金条的其实就是所有从 $X$ 出发的可行边中，连向的编号最小的人，我们只要能判断某条边是否为可行边，就能找到抢夺者。
在完备匹配中，假如边 $U-V$ 为可行边，只需要满足以下两个条件之一：
- $U-V$ 当前是匹配边（如果你是用 Dinic 求的最大匹配那么等价于 $U \to V$ 的残量为 $0$）。
- $U-V$ 是非匹配边，设当前 $U$ 与 $I$ 匹配，$V$ 与 $J$ 匹配，连接 $U-V$ 后，$I$ 和 $J$ 失去匹配，那么必须能找到一条从 $J$ 到 $I$ 的增广路才能保证最大匹配。
容易发现，假如我们把匹配边视为从右至左的有向边，非匹配边视为从左至右的（即跑完 Dinic 后的残量网络中残量为 $1$ 的单向边）。那么显然，从 $U$ 到 $V$ 有一条单向边，从 $I$ 到 $U$，从 $V$ 到 $J$ 也各有一条单向边，假如我们能再找到一条从 $V$ 到 $U$ 的路径，那么它满足如下性质：
- 这条路径长度肯定为奇数，因为二分图中没有奇环，而这条路径加上边 $U-V$ 就是一个环。
- 这条路径是从 $V$ 到 $U$ 的增广路，所以去除两端的两条边后它就是从 $J$ 到 $I$ 的增广路。
假如原先从 $V$ 到 $U$ 的增广路中匹配了 $e$ 条边，那么从 $J$ 到 $I$ 的增广路中就匹配了 $e-1$ 条边，加上新增的 $U-V$ 这条边，显然匹配数不变。
容易发现 $U$ 能到达 $V$，$V$ 又能到达 $U$，其实就是在说 $U,V$ 在同一个强连通分量里，我们对残量网络（如果你用的不是 Dinic 就自己手动给边定向）跑一遍强连通即可求解。
但是这道题不一定是完备匹配，上面的结论会出现一些问题。
- $U,V$ 二者之一可能本来就是非匹配点，不妨设 $V$ 是非匹配点，此时直接断开 $U$ 原来的匹配边，连接 $U-V$ 仍然是最大匹配。
- 即使当前 $U$ 与 $I$ 匹配，$V$ 与 $J$ 匹配，连接 $U-V$ 后，$I,J$ 失去匹配，我们也不一定非要找到从 $J$ 到 $I$ 的增广路，因为从 $I$ 到另一非匹配点的增广路同样可以得到一组包含 $U,V$ 的最大匹配。
所以我们不能直接当成完备匹配来做，但我们设右部某点为 $W$，汇点为 $T$，假如 $W$ 为非匹配点，$W \to T$ 的残量必定为 $1$，反之，假如 $W'$ 为匹配点，$W \to T$ 的残量必定为 $0$，即 $T \to W'$ 的残量为 $1$，换言之，存在一条路径 $W \to T \to W'$。假如二分图中有一条 $V$ 到 $U$ 的增广路，那么必定能从 $U$ 经过残量网络到达 $W$，进而到达 $V$，$U,V$ 仍在同一个强连通分量中。
在这一步中，跑一遍强连通的复杂度为 $O((n+m)+(nm-k))$，最终枚举求解的复杂度为 $O(m)$，故整个算法的复杂度是 $O((n+m)\sqrt{nm-k}+(n+m)+(nm-k)+m)$，差不多是 $O(n^2)$ 级别的，可以通过此题。
code
code
#include<iostream>
#include<algorithm>
#include<string.h>
#define mem(a,b) memset(a,b,sizeof(a))
#include<vector>
#include<queue>
#include<stack>
#define pbk(a) emplace_back(a)
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2010,inf=0x3f3f3f3f;
int n,m,p,x,K,ans[N];
void print(){
if(p==1){
forup(i,1,n){
printf("%d ",ans[i]+1);
}
puts("");
forup(i,1,m){
printf("%d ",ans[i+n]+1);
}
}else{//输出时注意反向输出
forup(i,1,m){
printf("%d ",ans[i+n]+1);
}
puts("");
forup(i,1,n){
printf("%d ",ans[i]+1);
}
}
}
struct Node{//链式前向星
int v,val,nxt;
}e[N*N],e2[N*N];
int head[N],cnt=1;//注意 cnt 从 1 开始才能用成对存储的技巧
void adde(int u,int v,int val){
e[++cnt]=Node{v,val,head[u]};head[u]=cnt;
}
vector<int> e1[N];
int st,ed;
void BuildGraph(){
forup(i,1,n){
e1[i].push_back(n);
e1[i].push_back(n+m+1);
sort(e1[i].begin(),e1[i].end());
if(i!=x){
int len=e1[i].size();
forup(j,1,len-1){
forup(k,e1[i][j-1]+1,e1[i][j]-1){
adde(i,k,1);adde(k,i,0);
}
}
}
}
st=n+m+1,ed=n+m+2;
forup(i,1,n){
if(i!=x){//建图时先不动关于 x 的边
adde(st,i,1);adde(i,st,0);
}
}
forup(i,n+1,n+m){
adde(i,ed,1);adde(ed,i,0);
}
}
int cur[N],lv[N];
bool bfs(){
mem(lv,-1);
lv[st]=0;
memcpy(cur,head,sizeof(head));//当前弧优化
queue<int> q;
q.push(st);
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,vol=e[i].val;
if(vol>0&&lv[v]==-1){
lv[v]=lv[u]+1;q.push(v);
}
}
}
return lv[ed]!=-1;
}
int dfs(int u=st,int flow=inf){
if(u==ed) return flow;
int rem=flow;
for(int& i=cur[u];i&&rem;i=e[i].nxt){
int v=e[i].v,vol=e[i].val;
if(vol>0&&lv[v]==lv[u]+1){
int c=dfs(v,min(vol,rem));
rem-=c;
e[i].val-=c;
e[i^1].val+=c;//“成对存储”技巧
}
}
return flow-rem;
}
int dinic(){//Dinic 板子
int res=0;
while(bfs()){
res+=dfs();
}
return res;
}
int belong[N],ist[N],dfn[N],low[N],cntdfn,csc;
stack<int> stk;
void Tarjan(int x){//Tarjan 强连通，没啥好说的
dfn[x]=low[x]=++cntdfn;stk.push(x);ist[x]=1;
for(int i=head[x];i;i=e[i].nxt) if(e[i].val==1){
int v=e[i].v;
if(!dfn[v]){
Tarjan(v);
low[x]=min(low[x],low[v]);
}else if(ist[v]){
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x]){
csc++;
while(stk.top()!=x){
belong[stk.top()]=csc;
ist[stk.top()]=0;
stk.pop();
}
belong[stk.top()]=csc;
ist[stk.top()]=0;
stk.pop();
}
}
void solve(){
memcpy(e2,e,sizeof(e));//复制一份方便还原
int bef=dinic();
memcpy(e,e2,sizeof(e2));
int len=e1[x].size();//加上和 x 有关的边
forup(j,1,len-1){
forup(k,e1[x][j-1]+1,e1[x][j]-1){
adde(x,k,1);adde(k,x,0);
}
}
adde(st,x,1);adde(x,st,0);
int aft=dinic();
if(aft==bef) return;//假如没有变化说明先手必败
forup(i,1,m+n+2){//跑强连通
if(!dfn[i]) Tarjan(i);
}
int mn=inf;
for(int i=head[x];i;i=e[i].nxt){//枚举从 x 出发的边，统计答案
if(e[i].v!=st&&e[i].v!=ed&&(e[i].val==0||belong[e[i].v]==belong[x])){
mn=min(mn,e[i].v);
}
}
ans[mn]=1;
ans[x]=-1;
}
signed main(){
n=read();m=read();p=read();x=read();K=read();
if(p==2) swap(n,m);//“不妨设 P=1”
ans[x]=1;
forup(i,1,K){
int u=read(),v=read();
if(p==2) swap(u,v);
e1[u].push_back(v+n);
}
BuildGraph();
solve();
print();
}