二分图题目类型总结与选讲
前言
自从上次的决策单调性小结和刚刚更新的莫队全家桶，已经很久没有写过正经的总结类文章了。
最近也是在复习二分图和网络流，于是借此契机水篇博客总结一下
二分图理论相关
二分图 (Bipartite graph)
定义
如果一张无向图的 $n$ 个节点可以分成 $A,B$ 两个非空集合，其中 $A\bigcap B=\varnothing$ ，并且在同一集合内的点都没有边相连，那么称这张图为一张二分图。
其中，$A，B$ 分别称为这张二分图的左部与右部。
性质
一张无向图是二分图，当且仅当途中不存在奇环。
二分图的判定
经典中的经典。
根据二分图的性质，我们可以使用染色法进行二分图的判定。
具体地，我们使用黑白两种颜色来对二分图进行染色。每次将相邻的两个节点染成不同的颜色。如果在过程中遇到已经被染色，但是现在需要染上另外一种颜色的情况下，那么这张图一定存在奇环，不是二分图。
//#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)}$
板子题，无细节
唯一要注意的就是开 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;
}给定一块棋盘，上面有一些点，问经过行行互换与列列互换能否实现所有对角线上都有点
目标状态是 $(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;
}经典套路了。
有石头的位置不能放。
石头分为硬石头和软石头，硬石头炸不穿，软石头能炸碎。
硬石头可以将一行或者一列分隔开，可以认为是一行新的和一列新的。
于是我们给每一个连续的极长不可扩展的一块一个新的编号。
之后横竖建边，跑最大匹配就好了。
//#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$ 。
- 重复上述过程
给定一些黑点白点，要求一个黑点连接一个白点，并且所有线段不相交
可以发现，如果黑白连线相交，我们可以通过交换的方式使得不相交，并且相交之后线段变短。
求解二分图最小权最大匹配。
把权值写成负数，然后跑最大权最大匹配就行了。
//#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$
二分图的最小点覆盖的点数 $=$ 二分图最大匹配的边数
简单记作：最小点覆盖等于最大匹配、
构造方法：
求出最大匹配
从左部每一个非匹配点出发，执行一次寻找增广路的过程，标记经过的节点。
取左部未被标记的节点与右部被标记的节点。
发现问题是这样的。
一颗小星星一定会出现在一行与一列的交汇点，所以可以选择在消灭行时消灭，也可以在消灭列时消灭。
只要有一个覆盖即可。
把小星星的坐标看成一条边的两个端点，只要其中一个节点被覆盖就达成了目的。
建图跑最大匹配，因为最小点覆盖等于最大匹配，所以直接输出就好了
//#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 完全问题。
定理
二分图最大独立集是 $=$ 总点数 $-$ 最大匹配数
去掉最小点覆盖就是最大独立集。
即最大独立集就是最小点覆盖关于全图点数的补集。
将图进行黑白染色，每次把“日”字格子的两角建边，跑最大独立集即可
#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;
}有两个国家，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’$ 上跑最小路径覆盖就可以了。
观察题面，发现一个人如果要答题的话，可以选择一条链全部进行回答。
由于贡献来自他和亲友团没有答到的题目中价值最小的。
对于一道相同的题目，显然再答一次不会有任何多出的贡献。
相当于对这张图进行最小链覆盖。
首先进行 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 定理
对于任意有限偏序集，其最长链中元素的数目必等于其最小长链划分中反链的数目。
即最长反链的大小等于最小可重链覆盖大小。
最长反链 $=$ 最小链覆盖
于是转化为求最小链覆盖。
由于最小链覆盖可以转化成最小路径覆盖，于是最小路径覆盖等于最大独立集，而最大独立集是最小点覆盖的补集，最小点覆盖等于最大匹配。
于是思路就理顺了，正常进行即可
首先进行 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;
}
二分图的最小支配集
选出一个点集，每个点要么被选择，要么和被选择的点相连
例题还没写，先咕着，写完再来补
二分图的必经边与可行边
先咕着，还没学会
