二分图题目类型总结与选讲

前言

自从上次的决策单调性小结和刚刚更新的莫队全家桶，已经很久没有写过正经的总结类文章了。

最近也是在复习二分图和网络流，于是借此契机~~水篇博客~~总结一下

二分图理论相关

二分图 (Bipartite graph)

定义

如果一张无向图的 $n$ 个节点可以分成 $A,B$ 两个非空集合，其中 $A\bigcap B=\varnothing$ ，并且在同一集合内的点都没有边相连，那么称这张图为一张二分图。

其中，$A，B$ 分别称为这张二分图的左部与右部。

性质

一张无向图是二分图，当且仅当途中不存在奇环。

二分图的判定

P1525 [NOIP2010 提高组] 关押罪犯

经典中的经典。

根据二分图的性质，我们可以使用染色法进行二分图的判定。

具体地，我们使用黑白两种颜色来对二分图进行染色。每次将相邻的两个节点染成不同的颜色。如果在过程中遇到已经被染色，但是现在需要染上另外一种颜色的情况下，那么这张图一定存在奇环，不是二分图。

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=1e5+5;

int n,m;

int head[maxn],to[maxn<<1],nxt[maxn<<1],w[maxn<<1],cnt;

inline void add(int u,int v,int val){
    nxt[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=val;
    head[u]=cnt;
}

int l=0,r=-INF,vis[maxn],now;

bool ok;

void dfs(int u,int tag){
    vis[u]=tag;
    for(re int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(w[i]>now){
			if(!vis[v])dfs(v,3-tag);
        	else if(vis[v]==tag){
	            ok=false;
	            return;
	        }
	     }
    }
}

inline bool check(int x){
    memset(vis,0,sizeof(vis));
    now=x;ok=1;
    for(re int i=1;i<=n&&ok;i++){
        if(!vis[i])dfs(i,1);
    }

    return ok;
}

inline int read(){
    int x=0, f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
    n=read();m=read();
    for(re int i=1,u,v,val;i<=m;i++){
        u=read();v=read();val=read();
        add(u,v,val);add(v,u,val);
        r=max(r,val);
    }

    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }

    printf("%d\n",l);



    return 0;
}

二分图的匹配

理论知识

匹配：任意两条边都没有公共顶点的边的集合被称为图的一组匹配。

最大匹配：在二分图中，包含边数最多的一组匹配被称为是二分图的最大匹配。

匹配边：对于任意一组匹配 $S$ ，属于 $S$ 的边被称为匹配边，否则为非匹配边。

匹配点：匹配边的端点被称为匹配点，否则是非匹配点。

增广路：在二分图上一条连接两个非匹配点的路径，使得非匹配边与匹配边在路径上交替出现。

增广路的性质：

长度是奇数
路径上单数号是非匹配边，双数号是匹配边。

于是得出一个性质：如果我们得到了一条增广路，可以将路径上的边全部取反，原来的匹配边变成非匹配边，非匹配边变成匹配边，匹配数会增加 $1$ 。

完备匹配（完美匹配）：给定一张左右部点数相同的二分图，如果此二分图的最大匹配包含恰好 $n$ 条匹配边，那么成此匹配为完备匹配（完美匹配）

多重匹配：给定一张左部点为 $n$ ，右部点为 $m$ ，的二分图，从中选择尽量多的边，使第 $i$ 个左部节点至多与 $k_{l_i}$ 条选出的边相连,第 $j$ 个右部点最多与 $k_{r_j}$ 条选出的边相连。

多重匹配是一个广义的匹配问题，二分图最大匹配是 $k_{l_i}=k_{r_j}=1$ 的特殊情况。

二分图的最大匹配

算法

匈牙利算法（增广路算法）

二分图的一组匹配 $S$ 是最大匹配，当且仅当图中不存在 $S$ 的增广路。

流程：

设开始的所有边都是非匹配边
寻找增广路，把路径上所有边的状态取反；
重复上面一步，直到图中不存在增广路

如何寻找增广路？

依次给每一个左部点寻找一个匹配的右部点，如果右部点没有匹配，那么直接匹配，否则，尝试给和右部点匹配的点寻找新的匹配，之后把这个右部点分给左部点。

代码简单好写：

bool find(int x){
    for(re int i=head[x];i;i=nxt[i]){
        int v=to[i];
        if(vis[v])continue;
        vis[v]=true;
        if(!match[v]||find(match[v])){
            match[v]=x;
            return true;
        }
    }
    return false;
}

int main(){
	for(re int i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(find(i))ans++;
        }
}

时间复杂度 $\mathcal{O(nm)}$

例题：P2756 飞行员配对方案问题

板子题，无细节

唯一要注意的就是开 long long

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define re register
const ll maxn = 5e5+5;

ll n,m,ans;
ll head[maxn],nxt[maxn],to[maxn],cnt,match[maxn];
bool vis[maxn];

inline void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}

bool find(ll u){
	for(ll i=head[u];i;i=nxt[i]){
		ll v=to[i];
		if(vis[v])continue;
		vis[v]=true;
		if(!match[v]||find(match[v])){
			match[v]=u;
			return true;
		}
	}
	return false;
}

inline ll read() {
    ll x = 0, f = 1;char ch = getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x * f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif

	n=read();m=read();
	ll x,y;
	while(~scanf("%lld%lld",&x,&y)){
		if(x==-1&&y==-1)break;
		add(x,y);
	}
	
	for(re ll i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(find(i))ans++;
	}
	
	printf("%lld\n",ans);
	
	for(ll i=n+1;i<=m;i++){
		if(match[i])printf("%lld %lld\n",match[i],i);
	}

	return 0;
}

P1129 [ZJOI2007] 矩阵游戏

给定一块棋盘，上面有一些点，问经过行行互换与列列互换能否实现所有对角线上都有点

目标状态是 $(1,1),(2,2),(3,3)…$ 都要有一个点。

于是我们可以把点看成是一条边，这条边连接了这个点的横纵坐标。

于是就是说每行和每一列都要有匹配。

可以发现交换两行或者两列的操作并不会影响匹配。

因为如果两个点一开始不在一行或者一列，那么无论怎么交换都不会出现在一行或者一列

就是说交换不影响匹配数。

于是我们就要求匹配数恰好为点数

建图的话每次把一个点的行号和列号连接起来。

可以看做是用第 $i$ 行第 $j$ 列的 $1$ 去交换同一行对角线上的 $1$ ；

求最大匹配即可：

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f
#define re register
const int maxn=4e4+5;

int T,n,ans;

int head[maxn],to[maxn<<1],nxt[maxn<<1],cnt;

inline void add(int u,int v){
    nxt[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
}

int match[maxn],a[205][205];

bool vis[maxn];

bool find(int x){
    for(re int i=head[x];i;i=nxt[i]){
        int v=to[i];
        if(vis[v])continue;
        vis[v]=true;
        if(!match[v]||find(match[v])){
            match[v]=x;
            return true;
        }
    }
    return false;
}

inline void init(){
    ans=0;
    memset(match,0,sizeof(match));
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
}

inline int read(){
    int x=0, f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
    T=read();
    while(T--){
        n=read();
        init();
        for(re int i=1;i<=n;i++){
            for(re int j=1;j<=n;j++){
                a[i][j]=read();
                if(a[i][j])add(i,j);
            }
        }

        for(re int i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(find(i))ans++;
        }

        ans>=n?puts("Yes"):puts("No");
    }
    

    return 0;
}

P2825 [HEOI2016/TJOI2016]游戏

经典套路了。

有石头的位置不能放。

石头分为硬石头和软石头，硬石头炸不穿，软石头能炸碎。

硬石头可以将一行或者一列分隔开，可以认为是一行新的和一列新的。

于是我们给每一个连续的极长不可扩展的一块一个新的编号。

之后横竖建边，跑最大匹配就好了。

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=2005;

int head[maxn],to[maxn],nxt[maxn],cnt;

inline void add(int u,int v){
	nxt[++cnt]=head[u];
	to[cnt]=v;
	head[u]=cnt;
}

int n,m,tot;

char mp[maxn][maxn];

int l[maxn][maxn],r[maxn][maxn];

bool vis[maxn];

int match[maxn],ans;

bool dfs(int u){
	for(re int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(vis[v])continue;
		vis[v]=true;
		if(!match[v]||dfs(match[v])){
			match[v]=u;
			return true;
		}
	}
	return false;
}


template<typename T>
inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    x*=f;
}

signed main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
	read(n),read(m);
	for(re int i=1;i<=n;i++){
		cin>>mp[i]+1;
	}

	for(re int i=1;i<=n;i++){
		for(re int j=1;j<=m;j++){
			if(mp[i][j]=='#')continue;
			if(j==1||mp[i][j-1]=='#')tot++;
			l[i][j]=tot;
		}
	}
	
	for(re int j=1;j<=m;j++){
		for(re int i=1;i<=n;i++){
			if(mp[i][j]=='#')continue;
			if(i==1||mp[i-1][j]=='#')tot++;
			r[i][j]=tot;
		}
	}
	
	for(re int i=1;i<=n;i++){
		for(re int j=1;j<=m;j++){
			if(mp[i][j]!='*')continue;
			add(l[i][j],r[i][j]);
		}
	}
	
	for(re int i=1;i<=tot;i++){
		memset(vis,false,sizeof(vis));
		if(dfs(i))ans++;
	}
	
	printf("%d\n",ans);



    return 0;
}

二分图的多重匹配

解决方案：

拆点：能连几条边就拆成几个点
如果只有一侧是多重的，那么直接让多重的一侧每个点执行 $k$ 次。
允许一个点被匹配多次，超过次数以后再寻求改变匹配
网络流（网络流大法吼啊！

还没写过，先咕着

二分图的带权匹配

给定一张二分图，每一条边都有一个权值，求出最大匹配，并要求边权和最大。

第一目的是最大匹配，其次是边权要求。

算法

KM算法

稠密图上效率很高
只能满足带权最大匹配一定是完备匹配的问题

交错树：如果在匹配过程中，从某个左部点出发寻找匹配失败，在 dfs 过程中，所经过的点及边共同构成了一棵树——交错树

交错树的根节点是左部节点，叶子节点也都是左部节点，奇数层是非匹配边，偶数层是匹配边。

顶点标记值（顶标）：给每一个左部点一个标记 $la_i$ ，右部点一个标记 $lb_i$ 。必须满足 $la_i+lb_i\ge w(i,j)$ .

相等子图：所有节点与满足 $la_i+lb_i = w(i,j)$ 的边构成的子图。

定理

若相等子图中存在完备匹配，那么这个完备匹配就是二分图的最大带权匹配

证明：

相等子图中，完备匹配的边权和就是顶标之和，而因为 $la_i+lb_i\ge w(i,j)$ ，所以权值无法扩展。

算法过程：

满足顶标定义的前提下，首先给每个顶点任意附顶标，之后不断扩大相等子图的规模，直到相等子图存在完备匹配。通常赋值为 $la_i=\max \limits_{1\le j\le n} {w(i,j}$ ，$lb_i=0$.
每找到一个相等子图，就用匈牙利算法求最大匹配。如果最大匹配不完备，就会形成交错树。
每次将交错树中所有左部点的顶标都减去一个 $delta$ ，右部点顶标都加上 $delta$ 。
重复上述过程

UVA1411 Ants

给定一些黑点白点，要求一个黑点连接一个白点，并且所有线段不相交

可以发现，如果黑白连线相交，我们可以通过交换的方式使得不相交，并且相交之后线段变短。

求解二分图最小权最大匹配。

把权值写成负数，然后跑最大权最大匹配就行了。

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=105;
#define debug cerr<<"!!!!!!!!!!!!!!!!!!!!!!!!!"<<endl; 

int n;

double la[maxn],lb[maxn];

int match[maxn];

double upd[maxn],delta;

bool va[maxn],vb[maxn];

double xl[maxn],yl[maxn];

double xr[maxn],yr[maxn];

double w[maxn][maxn];

const double eps=1e-8;

inline double dis(double x,double y,double xx,double yy){
    return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}

bool dfs(int x){
    va[x]=true;
    for(re int y=1;y<=n;y++){
        if(!vb[y]){
            if(fabs(la[x]+lb[y]-w[x][y]<eps)){
                vb[y]=true;
                if(!match[y]||dfs(match[y])){
                    match[y]=x;
                    return true;
                }
            }
            else upd[y]=min(upd[y],la[x]+lb[y]-w[x][y]);
        }
    }
    return false;
}

inline void KM(){
	memset(match,0,sizeof(match));
    for(re int i=1;i<=n;i++){
        la[i]=-INF;lb[i]=0;
        for(re int j=1;j<=n;j++){
            la[i]=max(la[i],w[i][j]);
        }
    }
    
    for(re int i=1;i<=n;i++){
        while(true){
            memset(va,0,sizeof(va));
            memset(vb,0,sizeof(vb));
            for(re int j=1;j<=n;j++)upd[j]=INF;
            if(dfs(i))break;
            delta=INF;
            for(re int j=1;j<=n;j++){
                if(!vb[j])delta=min(delta,upd[j]);
            }
            for(re int j=1;j<=n;j++){
                if(va[j])la[j]-=delta;
                if(vb[j])lb[j]+=delta;
            }
        }
    }
    
    for(re int i=1;i<=n;i++){
        printf("%d\n",match[i]);
    }
}


template<typename T>
inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    x*=f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
	while(~scanf("%d",&n)&&n){
	    for(re int i=1;i<=n;i++){
	        scanf("%lf%lf",&xl[i],&yl[i]);
	    }
	    for(re int i=1;i<=n;i++){
	        scanf("%lf%lf",&xr[i],&yr[i]);
	    }
	    
	    for(re int i=1;i<=n;i++){
	        for(re int j=1;j<=n;j++){
	            w[j][i]=-dis(xl[i],yl[i],xr[j],yr[j]);
	        }
	    }
	    
	    KM();
	}
    

	return 0;
}

二分图的覆盖与独立集

二分图的最小点覆盖

给定一张二分图，求出一个最小的点集 $S$ 。使得图中任意一条边都有至少一个端点属于 $S$

二分图的最小点覆盖的点数 $=$ 二分图最大匹配的边数

简单记作：最小点覆盖等于最大匹配、

构造方法：

求出最大匹配
从左部每一个非匹配点出发，执行一次寻找增广路的过程，标记经过的节点。
取左部未被标记的节点与右部被标记的节点。

P7368 [USACO05NOV]Asteroids G

发现问题是这样的。

一颗小星星一定会出现在一行与一列的交汇点，所以可以选择在消灭行时消灭，也可以在消灭列时消灭。

只要有一个覆盖即可。

把小星星的坐标看成一条边的两个端点，只要其中一个节点被覆盖就达成了目的。

建图跑最大匹配，因为最小点覆盖等于最大匹配，所以直接输出就好了

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=25005;

int n,k,ans;

int head[maxn],to[maxn],nxt[maxn],cnt;

inline void add(int u,int v){
    nxt[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
}

int match[maxn];

bool vis[maxn];

bool dfs(int x){
    for(re int i=head[x];i;i=nxt[i]){
        int v=to[i];
        if(vis[v])continue;
        vis[v]=true;
        if(!match[v]||dfs(match[v])){
            match[v]=x;
            return true;
        }
    }
    return false;
}

inline int read(){
    int x=0, f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
    n=read();k=read();
    for(re int i=1,x,y;i<=k;i++){
        x=read();y=read();
        add(x,y);
    }

    for(re int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }

    printf("%d\n",ans);


    return 0;
}

P6062 [USACO05JAN]Muddy Fields G

每块泥地要不然被横着的一行盖住，要不被纵着的一列盖住。

木板不能盖住干净地面，所以木板所遮盖的必然是一块极大不可扩展的泥地方格。

预处理出所有的横着的极大方格和纵着的极大方格，横纵建边。

求解最小点覆盖

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=1005;
const int maxm=55;

int n,m,ans;

char a[55][55];

int head[maxn],to[maxn],nxt[maxn],cnt;

inline void add(int u,int v){
    nxt[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
}

int L[maxm][maxm],R[maxm][maxm],cnt1,cnt2;

int match[maxn];

bool vis[maxn];

bool dfs(int x){
    for(re int i=head[x];i;i=nxt[i]){
        int v=to[i];
        if(vis[v])continue;
        vis[v]=true;
        if(!match[v]||dfs(match[v])){
            match[v]=x;
            return true;
        }
    }
    return false;
}

inline int read(){
    int x=0, f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
    n=read();m=read();

    for(re int i=1;i<=n;i++){
        cin>>a[i]+1;
    }

    for(re int i=1;i<=n;i++){
        for(re int j=1;j<=m;j++){
            if(a[i][j]=='*'){
                if(j==1||a[i][j-1]=='.')L[i][j]=++cnt1;
                else L[i][j]=cnt1;
            }
        }
    }

    for(re int i=1;i<=m;i++){
        for(re int j=1;j<=n;j++){
            if(a[j][i]=='*'){
                if(j==1||a[j-1][i]=='.')R[j][i]=++cnt2;
                else R[j][i]=cnt2;
                add(L[j][i],R[j][i]);
            }
        }
    }

    for(re int i=1;i<=cnt1;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }

    printf("%d\n",ans);



    return 0;
}

二分图最大独立集

独立集：给定一张二分图，将其划分成若干个点集，使得任意两点之间没有边相连。

最大独立集：独立集里面最大的那个

团：任意两点都有边相连的子图

最大团：最大的那个

无向图的最大团等于其补图的最大独立集

对于一般无向图，求解最大团，最大独立集是 NP 完全问题。

定理

二分图最大独立集是 $=$ 总点数 $-$ 最大匹配数

去掉最小点覆盖就是最大独立集。

即最大独立集就是最小点覆盖关于全图点数的补集。

P3355 骑士共存问题

将图进行黑白染色，每次把“日”字格子的两角建边，跑最大独立集即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
const int dx[8]={-1,-2,-2,-1,1,2,2,1};
const int dy[8]={-2,-1,1,2,2,1,-1,-2};
int n,m,cnt,ans;

bool mapp[2005][2005];
bool vis[100005];

int match[100005],head[maxn];

vector <int> node;

struct edge{
	int next,to;
}e[maxn];

inline void add(int u,int v){
	e[++cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}

bool find(int u){
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(!vis[v]){
			vis[v]=1;
			if(match[v]==-1||find(match[v])){
				match[v]=u;
				return 1;
			}
		} 
	}
	return 0;
}

int main(){
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		mapp[x][y]=1;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!mapp[i][j]&&(i+j)%2){//遍历图，如果没有障碍就黑白染色
				node.push_back(n*(i-1)+j);//把行列抻直了使用1—n^2作为编号
				for(int k=0;k<8;k++){//对可以扩展出的8个可能的日字的对角点连边
					int xx=i+dx[k];
					int yy=j+dy[k];
					if(xx<=0||xx>n||yy<=0||yy>n)continue;
					if(!mapp[xx][yy]){
						add(n*(i-1)+j,n*(xx-1)+yy);
					}
				}
			}
		}
	}
	
	memset(match,-1,sizeof(match));
	for(int i=0;i<node.size();i++){//冲冲冲！
		memset(vis,0,sizeof(vis));
		ans+=find(node[i]);
	}
	
	cout<<n*n-m-ans;
	
	return 0;
}

P2423 [HEOI2012]朋友圈

有两个国家，A 国家内部两人编号一奇一偶就连边，B 内部同奇数都连边，同偶数都连边。

A 和 B 之间可能有边。

求最大团。

看到最大团，我们考虑进行补图转化，也就是想办法求出最大独立集。

考虑补图：

对于 A补图：

A 点的奇数点构成了一个团，偶数点构成一个团。

对于 B补图：

奇数点和偶数点构成了二分图。

于是问题变成了在补图上找最大独立集。

由于 A 补图有两个团，所以我们选择方案极其有限：一个都不选，从其中的一个团选出一个，两个团各选一个。

设取出的这两个点分别是 $x,y$
我们在 B 补图中删去与这两点有边相连的 B 补图点，之后在 B 补图中剩余点跑最大独立集就可以了。

为什么正确呢？

首先最大独立集对于 B 补图一定是正确的。

考虑带上 A 补图中的点。

由于 A 补图中有两个团，所以同一个团中最多选出一个节点，才能保证不与其他点相连。

每次选出 A 补图中的人就把 B 补图中相连的点删去，这保证了 B 补图中点不与 A 补图中点相连。

所以这样建出的图是正确的，且他的原图所有点都互相连接。

细节是双向边。

注意这道题目中其实暗中规定好了左部点和右部点，应当直接默认奇数点是左部点，否则会多出一倍的常数。

还需要一个优化。

本题极度卡常，所以常规的匈牙利算法已经不足以满足我们的需求。

为什么？

可以发现每次找到一个节点准备进行增广时，都需要把 $vis$ 清空。

效率很低。

所以我们引入时间戳的概念来进行优化。

具体实现看代码

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=3005;

int T,ans;

int n1,n2,A[maxn],B[maxn],m; 

int mp[maxn][maxn];

vector <int> Bmp[maxn];

int vis[maxn],tim,match[maxn];

int flag[maxn],t;

bool dfs(int x){
	for(unsigned int i=0;i<Bmp[x].size();i++){
		int v=Bmp[x][i];
		if(vis[v]!=tim&&flag[v]==t){//时间戳优化
			vis[v]=tim;
			if(!match[v]||dfs(match[v])){
				match[v]=x;
				return true;
			}
		}
	}
	return false;
}

inline int solve0(){//如果一个都不选
	int res=0;
	for(re int i=1;i<=n2;i++){
		if(B[i]&1){//定好左部点
			tim++;//时间戳优化
			if(dfs(i))res++;
		}
	}
	res=n2-res;
	
	return res;
}

inline int solve1(){//如果只选一个
	int res=-INF;
	for(re int i=1;i<=n1;i++){
		t++;int sum=0,nn=0;
		memset(match,0,sizeof(match));
		for(re int j=1;j<=n2;j++){
			if(mp[i][j])flag[j]=t,nn++;//删除B补图中相连的点
		}
		for(re int j=1;j<=n2;j++){
			if(flag[j]==t&&(B[j]&1)){
				tim++;//时间戳
				if(dfs(j))sum++;
			}
		}
		res=max(res,nn-sum+1);
	}
	
	return res;
}

inline int solve2(){//如果选两个
	int res=-INF;
	for(re int i=1;i<=n1;i++){
		for(re int j=i+1;j<=n1;j++){
			if((A[i]^A[j])&1){
				t++;int sum=0,nn=0;
				memset(match,0,sizeof(match));
				for(re int k=1;k<=n2;k++){
					if(mp[i][k]&&mp[j][k])flag[k]=t,nn++;//删除相连的点
				}
				for(re int k=1;k<=n2;k++){
					if(flag[k]==t&&(B[k]&1)){
						tim++;//时间戳
						if(dfs(k))sum++;
					}
				}
				res=max(res,nn-sum+2);
			}
		}
	}
	return res;
}

inline int calc(int x){
	int res=0;
	while(x){
		res+=x&1;
		x>>=1;
	}
	return res;
}

template<typename T>
inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    x*=f;
}

signed main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
	read(T);
	while(T--){
		memset(mp,0,sizeof(mp));ans=-INF;
		read(n1),read(n2),read(m);
		for(re int i=1;i<=n1;i++)read(A[i]);
		for(re int i=1;i<=n2;i++)read(B[i]);
		for(re int i=1,u,v;i<=m;i++){
			read(u),read(v);
			mp[u][v]=mp[v][u]=1;
		}
		for(re int i=1;i<=n2;i++){
			if(B[i]&1){
				for(re int j=1;j<=n2;j++){
					if(!(B[j]&1)&&!(calc(B[i]|B[j])&1))Bmp[i].push_back(j),Bmp[j].push_back(i);
				}
			}
		}
		
		ans=max(ans,solve0());
		ans=max(ans,solve1());
		ans=max(ans,solve2());
		
		printf("%d\n",ans);
	}
	
	
    return 0;
}

DAG 的最小路径覆盖（多条链不能有公共点）

给定一张 DAG ，要求用尽量少的不相交的简单路径，覆盖 DAG 的所有顶点，每个顶点恰好覆盖一次。

将原来 DAG 中每一个点拆点，拆成 $x,x+n$ 两个点。

以 $1-n$ 为左部点，$n+1-2\times n$ 为右部点，建立二分图，对于原图中每一条有向边 $(x,y)$ 在二分图左部点 $x$ 与右部点 $y+n$ 连边。

这个二分图被称为原 DAG 的拆点二分图，记为 $G_2$ 。

定理

DAG $G$ 的最小路径覆盖包含的路径条数 $=$ $n-G_2$ 的最大匹配数。

最小路径覆盖等于最大独立集

证明

一开始每个点都是独立的一条路径，总共有 $n$ 条不相交路径。每次在二分图中找一条匹配边就相当于把两条路径合并成了一条，就是总路径数减少了 $1$ ，所以找到了几条匹配边，路径就减少了多少。于是最小路径覆盖包含的路径条数 $=$ $n-G_2$ 的最大匹配数

DAG 的最小链覆盖（多条链可以重叠）

DAG 的最小链覆盖也被称为最小路径可重复点覆盖。

考虑一个 DAG 上的两条相交路径

_suppose_：

路径 $a$ : $…\rightarrow x\rightarrow p\rightarrow y \rightarrow …$

路径 $b$ ： $…\rightarrow u\rightarrow p\rightarrow v\rightarrow…$

他们有公共交点 $p$ 。

为了防止相交我们可以在 $x\rightarrow y$ 直接连一条新边，这样就不用走同一条路了。

于是我们首先使用 floyd 传递闭包得到新的 DAG $G’$

之后直接在 $G’$ 上跑最小路径覆盖就可以了。

P4589 [TJOI2018]智力竞赛

观察题面，发现一个人如果要答题的话，可以选择一条链全部进行回答。

由于贡献来自他和亲友团没有答到的题目中价值最小的。

对于一道相同的题目，显然再答一次不会有任何多出的贡献。

相当于对这张图进行最小链覆盖。

首先进行 floyd 传递闭包。

对于我们需要求出的没有被答到的题目最小价值最大，显然需要二分。

每次检查一个 $mid$ ，把小于 $mid$ 的值放入新的邻接矩阵中，之后对这个新的邻接矩阵求解最小路径覆盖。

最小路径覆盖等于最大独立集，最大独立集等于最小点覆盖的补集，最小点覆盖等于最大匹配。

于是求出最大匹配之后，算出最大独立集，从而得出最小路径覆盖，再与 $n+1$ 个人进行比较，得出结论即可。

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=1005;

int n,m;

int val[maxn];

int g[maxn][maxn],f[maxn][maxn];

inline void floyd(){
	for(re int k=1;k<=m;k++){
		for(re int i=1;i<=m;i++){
			for(re int j=1;j<=m;j++){
				g[i][j]|=g[i][k]&g[k][j];
			}
		}
	}
}

int l=INF,r=-INF;

int match[maxn];

bool vis[maxn];

bool dfs(int u){
	for(re int v=1;v<=m;v++){
		if(f[u][v]&&!vis[v]){
			vis[v]=true;
			if(!match[v]||dfs(match[v])){
				match[v]=u;
				return true;
			}
		}
	}
	return false;
}

inline bool check(int x){
	memset(f,0,sizeof(f));
	memset(match,0,sizeof(match));
	int cnt=0,res=0;
	for(re int i=1;i<=m;i++){
		for(re int j=1;j<=m;j++){
			if(val[i]<x&&val[j]<x)f[i][j]=g[i][j];
		}
	}
	for(re int i=1;i<=m;i++)if(val[i]<x)cnt++;
	for(re int i=1;i<=m;i++){
		memset(vis,0,sizeof(vis));
		if(dfs(i))res++;
	}
	
	return n+1>=cnt-res;//还要包含小豆自己呢 
}


template<typename T>
inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    x*=f;
}

signed main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
	read(n),read(m);
	for(re int i=1,k;i<=m;i++){
		read(val[i]),read(k);
		l=min(l,val[i]),r=max(r,val[i]);
		while(k--){
			int a;
			read(a);
			g[i][a]=1;
		}
	}

	floyd();
	
	if(check(r+1)){
		puts("AK");
		return 0;
	}
	
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	
	printf("%d\n",l);


    return 0;
}

二分图的最长反链

最长反链：一张有向无环图的最长反链为一个集合 $ S\subseteq V$，满足对于 $S$ 中的任意两个不同的点 $u, v \in S(u \ne v)$，$u$ 不能到达 $v$，$v$ 也不能到达 $u$，且 $S$ 的大小尽量大。

Dilworth 定理

对于任意有限偏序集，其最长链中元素的数目必等于其最小长链划分中反链的数目。

即最长反链的大小等于最小可重链覆盖大小。

最长反链 $=$ 最小链覆盖

于是转化为求最小链覆盖。

由于最小链覆盖可以转化成最小路径覆盖，于是最小路径覆盖等于最大独立集，而最大独立集是最小点覆盖的补集，最小点覆盖等于最大匹配。

于是思路就理顺了，正常进行即可

P4298 [CTSC2008]祭祀

首先进行 floyd 传递闭包，转化为最小路径覆盖问题。

之后跑一次最大匹配，它的补集大小就是答案。

本题还要求构造答案。

首先需要构造最大独立集。

构造最大独立集可以通过构造最小点覆盖，之后进行补集转化来实现。

跑完最大匹配之后，对于每一个没有匹配的左部点，以他为起点进行一次尝试增广的 dfs 操作（必定会失败），过程中记录下经过的点。

最后取出左部被标记的点且右部没有标记的点（最小点覆盖是需要取出左部没有标记的点与右部被标记的点的并集，但是由于我们构造的是其补集，所以左部被标记的点与右部没有被标记的点的交集）

于是我们构造出了最大独立集。

由最小路径覆盖等于最大独立集，相当于我们构造出了最小路径覆盖。

由于我们已经进行了传递闭包，所以等价于我们构造出了最小链覆盖，也就是最长反链的方案。

对于问题 $3$ ，要求我们满足最长反链最大的前提下，找到所有可能位置。

考虑一个已经求出的最长反链，如果从最长反链中去除一个点，最长反链大小会减小 $1$ 。

于是我们可以首先钦定一个点在最长反链里，之后我们删除和这个点有偏序关系的所有点，之后再求一次最长反链，并且判断最长反链长度是否比原来小 $1$，从而判断这个点在不在最长反链中。

本题极好，一定要把思路理顺，代码并不难写。

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=105;

int n,m;

int mp[maxn][maxn];

int match[maxn];

bool vis[maxn],del[maxn];

inline void floyd(){
    for(re int k=1;k<=n;k++)
        for(re int i=1;i<=n;i++)
            for(re int j=1;j<=n;j++)
                mp[i][j]|=mp[i][k]&mp[k][j];

}

int cnt1,cnt2,tmp;

bool dfs(int x){
    for(re int y=1;y<=n;y++){
        if(mp[x][y]&&!vis[y]&&!del[y]){
            vis[y]=true;
            if(!match[y]||dfs(match[y])){
                match[y]=x;
                return true;
            }
        }
    }
    return false;
}

bool flag[maxn][2];

void try_to_dfs(int x){
    flag[x][0]=true;
    for(re int y=1;y<=n;y++){
        if(mp[x][y]&&match[y]!=x&&!flag[y][1]){
            flag[y][1]=true;
            if(match[y]!=0)try_to_dfs(match[y]);
        }
    }
}

bool used[maxn];

inline void solve2(){
    for(re int i=1;i<=n;i++)used[match[i]]=true;
    for(re int i=1;i<=n;i++){
    	if(!used[i])try_to_dfs(i);
	}
	for(re int i=1;i<=n;i++){
        if(!(!flag[i][0]||flag[i][1]))printf("1");else printf("0");
        //或者可以写成  flag[i][0]&&!flag[i][1]
    }
    
    puts("");
}

inline void solve3(){
    for(re int i=1;i<=n;i++){
        memset(del,0,sizeof(del));
        memset(match,0,sizeof(match));
        cnt2=0,tmp=n;
        for(re int j=1;j<=n;j++){
            if(mp[i][j]||mp[j][i]||i==j)del[j]=true,tmp--;
        }
        for(re int j=1;j<=n;j++){
            if(del[j])continue;
            memset(vis,0,sizeof(vis));
            if(dfs(j))cnt2++;
        }
        printf("%d",tmp-cnt2==n-cnt1-1);
    }
}

template<typename T>
inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    x*=f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
    read(n),read(m);
    for(re int i=1,u,v;i<=m;i++){
        read(u),read(v);
        mp[u][v]=1;
    }

    floyd();

    for(re int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))cnt1++;
    }

    printf("%d\n",n-cnt1);
    
    solve2();

    solve3();


    return 0;
}

二分图的最小支配集

选出一个点集，每个点要么被选择，要么和被选择的点相连

例题还没写，先咕着，写完再来补

二分图的必经边与可行边

先咕着，还没学会