「LibreOJ Round #6」花札

一边听鸡汤一边写题解，真是太难以形容了。

传送门

把两个人的牌看成二分图的两侧，按照题目要求连边，之后就变成了一个二分图博弈的模型。

我以前从没听过这个东西。

二分图模型的结论是：先手必胜的条件是这个点一定不在最大匹配中。

证明好像是这样：

设一开始这个点在左边，如果它不在某一个最大匹配（设他为LI）中，那么它下一步一定会走到一个在LI中的点（称这种点为成功点），从这个成功点可以沿着LI中的路径走到左侧的另一个成功点（称这种走法为成功之路）。那么在这个成功点匹配的点走的下一步一定是成功之路，否则就找到了一条增广路，LI就可以变得更大（LI大成功）。

那么一直这样走下去由于这个最大匹配LI是从右边开始走的，所以会停在左边，后手无路可走（显然它失败了）。

而先手想要成功，就必须使起点在所有的最大匹配中（称这种情况为无LI）。

关于快速找出必胜起点的方法（成功の捷径）

可以去找一定失败的点，那么我们需要先跑一遍最大流，得到任意一个LI的残量网络。

说不清楚，引用学姐的好了

1.从S出发,走容量不为0的边所能到达的属于X集合的点。能到达点可以分成两类：一是非匹配点(直接到达),二是经过一个非匹配点,然后走一条类似增广路所到达的匹配点(即可以将这条路上的匹配边和非匹配边翻转得到另一组解,而这条路的终点就是另一组解中的非匹配点)
2.从T出发，沿反向弧为0的边走所能到达的属于Y集合的点。能到达的点也可以分成两类，与上面S的分析方法类似。
————————————————
版权声明：本文为CSDN博主「clover_hxy」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/clover_hxy/article/details/71106568

本题的话第一条就够了。

#include<cstdio>
#include<iostream>
using namespace std;
struct node{
    int next,to,z;
}w[2000001];
int fw[100001],head[100001],m;
int heap,tail,cnt,team[100001];
int deep[100001],o[100001],n,c,d;
int tim,num;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},flag,turn;
inline void add(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; w[cnt].z=1;
    head[x]=cnt; swap(x,y);
    w[++cnt].next=head[x];
    w[cnt].to=y; w[cnt].z=0;
    head[x]=cnt;
}
inline bool bfs(){
    int x;
    heap=tail=1; tim++; o[0]=tim;
    deep[0]=1; team[heap]=0;
    while (heap<=tail){
        x=team[heap];
        for (int i=head[x]; i; i=w[i].next){
            if (w[i].z>0&&o[w[i].to]!=tim){
                team[++tail]=w[i].to;
                o[w[i].to]=tim;
                deep[w[i].to]=deep[x]+1;
            }
        }
        heap++;
    }
    return (o[1]==tim);
}
int dfs(int x,int l){
    if (!l||(x==1)) return l;
    int used=0,z,minn;
    for (int i=head[x]; i; i=w[i].next){
        if (w[i].z&&deep[w[i].to]==deep[x]+1){
            minn=min(l-used,w[i].z);
            z=dfs(w[i].to,minn);
            if (z){
                w[i].z-=z; w[i^1].z+=z;
                used+=z; if (l==used) break;
            }
        }
    }
    if (!used) deep[x]=0;
    return used;
}
void dfs1(int x){
    fw[x]=1;
    for (int i=head[x]; i; i=w[i].next)
        if (w[i].z&&!fw[w[i].to]) dfs1(w[i].to);
}
int main(){
    int x,y;
    scanf("%d%d%d",&c,&d,&n);
    cnt=1; num=c+d+1;
    for (int i=1; i<=n; i++){
        scanf("%d%d",&x,&y);
        num++; add(0,num);
        add(num,x+1),add(num,y+c+1);
    }
    scanf("%d",&m);
    for (int i=1; i<=m; i++){
        scanf("%d%d",&x,&y);
        num++; add(num,1);
        add(x+1,num),add(y+c+1,num);
    }
    while (bfs()) dfs(0,1e9);
    dfs1(0);
    for (int i=1; i<=n; i++)
        printf("%d\n",fw[i+c+d+1]^1);
    return 0;
}