定义
二分图：可以把点集分为两部分\(A,B\),其中\(A\)，\(B\)内部不存在连边的图
二分图的确立，当且仅当图中不存在奇环
Pf：黑白染色
概念：
- 匹配：\(A,B\)一一对应，不存在相邻的边的边集
- 点覆盖：点集\(S\)满足每条边至少存在一点位于\(S\)
- 独立集：点集\(S\)满足每条边至多存在一点位于\(S\)
- 边覆盖：边集\(E\)满足每个顶点至少存在一条边位于\(E\)
- 路径覆盖（链）：在图中找路径使得每个节点在一条路径上
- 团：点集\(S\)满足其中所有点都相互连通
- 反链：点集\(S\)满足\(S\)中所有点互不联通
匈牙利
求二分图中最大匹配
bool dfs(int u) {
for(auto v:V[u]) {
if(fl[v]!=lim) {
fl[v]=lim;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
时间复杂度\(O(nm)\)
増广路
（虚边表示非匹配边，实边表示匹配边）
其中最后图上的増广路必须满足匹配边>=非匹配边（否则会有空余的边，这不是最大匹配）
特殊的情况：从非匹配点开始走到的都是匹配点，非匹配边-匹配边交叉（正好为偶数条边）
常见关系：
|最大匹配|=|最小点覆盖|
Pf:如果除最大匹配外还存在某条边没被覆盖，显然匹配数应+1，所以最大匹配是点覆盖，故|最大匹配|>=|最小点覆盖|
匹配的定义告诉我们，覆盖的边和边之间没有交点，所以不可能存在更小的点覆盖，即证
最小点覆盖的方案构造：先求出最大匹配，从左边未匹配点开始，走未匹配边到右边匹配点（一定是），走匹配边到左边的匹配点...沿着路径打标记
左边点集中未出现的点和右边点集中出现的点是最小点覆盖
说明：一个图可以被分成若干条増广路，而増广路有两种情况
 
前者（存在未匹配点）统计右节点优，后者为了方便统计左节点
点覆盖与独立集对应互补，最大独立集=G-最小点覆盖
Pf：由定义可以发现
对于不存在孤立点的图，|最大匹配|+|最小边覆盖|=|V|
Pf:不妨设节点数为\(n\),最大匹配数为\(m\)
一条边至多覆盖2个节点，所以显然要将匹配边全覆盖，之后剩下的节点只能有一条边逐一覆盖
则\(2m+t=n,m+t=|\text{最小边覆盖}|\)，即证
构造：同上
最大团=补图的最大独立集
Pf 定义
|最小不可重链覆盖|=n-|最大匹配|
Pf：开始时每个点裂成入点和出点，把每个点看作一条链，每次匹配入点和出点（即连边合并），链会减1，即证
最小可重链覆盖可以转化为最小不可重链覆盖
将点\(i\)能到达的所有点都与\(i\)相连即可（最优的情况下，每个点只需要经过一次）
|最长反链|=|最小可重链覆盖|
最长反链方案构造：先按上述求出最大独立集，再求出入点和出点都在最大独立集上的点
解题思路：
难点往往在构造二分图
通常行列，或者没有奇环的图。。。
例题1
消除格子
行列分开，求最小点覆盖，等于最大匹配
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=505*505;
int n,K,to[M],nxt[M],he[N],cnt,ma[N];
bool fl[N];
inline void add(int u,int v) {
to[++cnt]=v,nxt[cnt]=he[u],he[u]=cnt;
}
bool dfs(int u) {
for(int e=he[u];e;e=nxt[e]) {
int v=to[e];
if(!fl[v-n]) {
fl[v-n]=1;
if(!ma[v-n]||dfs(ma[v-n])) {
ma[v-n]=u; return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&K);
for(int i=1;i<=K;i++) {
int x,y; scanf("%d%d",&x,&y);
add(x,y+n);
}
int ans=0;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans++;
}
printf("%d\n",ans);
return 0;
}
例题2
出租车订单
根据能否连载连边，然后求最小不可重链覆盖
注意>=1这种细节
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,a[N],b[N],c[N],d[N],t[N],ma[N];
bool fl[N];
char s[10];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main(){
int T; scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%s%d%d%d%d",s+1,&a[i],&b[i],&c[i],&d[i]);
int h=(s[1]-'0')*10+s[2]-'0',m=(s[4]-'0')*10+s[5]-'0';
t[i]=h*60+m;
}
for(int i=1;i<=n;i++) {
int tmp=t[i]+abs(c[i]-a[i])+abs(b[i]-d[i]);
V[i].clear();
for(int j=1;j<=n;j++) {
if(i!=j&&t[j]-tmp>=abs(a[j]-c[i])+abs(b[j]-d[i])+1) {
V[i].push_back(j);
}
}
}
memset(ma,0,sizeof(ma));
int ans=n;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans--;
}
printf("%d\n",ans);
}
return 0;
}
例题3
Luogu P1129 [ZJOI2007] 矩阵游戏
首先发现横纵互不干扰（随意换顺序）
接着发现横纵分开后只需要横不需要纵，
最后发现只要不同列都有不同行的1即可
所以行和列拆开，判断最大匹配是否为\(n\)
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,ma[N];
bool fl[N];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main(){
int T; scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
V[i].clear();
for(int j=1;j<=n;j++) {
int op; scanf("%d",&op);
if(op) V[i].push_back(j);
}
}
memset(ma,0,sizeof(ma));
int ans=0;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans++;
}
if(ans==n) puts("Yes");
else puts("No");
}
return 0;
}
例题5
Luogu P4136 谁能赢呢？
把图拆成\(1\times 2\)的骨牌分组，判断什么时候是先手开骨牌的头，还是后手开骨牌的头，谁开骨牌头谁输
可以理解成有一副二分图，如果某人先手时不巧从未匹配点开始，他便输了，因为要么之后没有点，要么之后所有点都完美匹配了，后手只需要沿着匹配边走即可
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
scanf("%d",&n);
while(n) {
if(n&1) puts("Bob");
else puts("Alice");
scanf("%d",&n);
}
puts("");
}
例题6
Luogu P4055 [JSOI2009]游戏
多了限制，另外让你求初始点
由上题可以发现，先手下在某个最大匹配的未匹配点上，之后后手无论往哪儿走，始终落在存在匹配边的匹配点上，先手只需要沿着匹配边走即可
而如果先手下的位置一定是匹配点，那么后手只需要沿匹配边走即可，因为先手无论如何都会落在存在匹配边的匹配点上
所以考虑如何找最大匹配的未匹配点求并
只需要从每个未匹配点开始访问増广路，访问到的节点都可以成为最大匹配的未匹配点
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,m,ma[N];
bool fl[N],ans[N];
char s[105][105];
vector<int>V[N];
inline int id(int i,int j) {
return (i-1)*m+j;
}
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
void dgs(int u) {
ans[u]=1;
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1; dgs(ma[v]);
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(i+j&1&&s[i][j]=='.') {
if(s[i-1][j]=='.') {
V[id(i,j)].push_back(id(i-1,j));
}
if(s[i][j-1]=='.') {
V[id(i,j)].push_back(id(i,j-1));
}
if(s[i+1][j]=='.') {
V[id(i,j)].push_back(id(i+1,j));
}
if(s[i][j+1]=='.') {
V[id(i,j)].push_back(id(i,j+1));
}
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
if(i+j&1&&s[i][j]=='.') {
memset(fl,0,sizeof(fl));
dfs(id(i,j));
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
V[id(i,j)].clear();
if(!(i+j&1)&&ma[id(i,j)]) {
ma[ma[id(i,j)]]=id(i,j);
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(i+j&1&&s[i][j]=='.') {
if(s[i-1][j]=='.'&&id(i-1,j)!=ma[id(i,j)]) {
V[id(i,j)].push_back(id(i-1,j));
V[id(i-1,j)].push_back(id(i,j));
}
if(s[i][j-1]=='.'&&id(i,j-1)!=ma[id(i,j)]) {
V[id(i,j)].push_back(id(i,j-1));
V[id(i,j-1)].push_back(id(i,j));
}
if(s[i+1][j]=='.'&&id(i+1,j)!=ma[id(i,j)]) {
V[id(i,j)].push_back(id(i+1,j));
V[id(i+1,j)].push_back(id(i,j));
}
if(s[i][j+1]=='.'&&id(i,j+1)!=ma[id(i,j)]) {
V[id(i,j)].push_back(id(i,j+1));
V[id(i,j+1)].push_back(id(i,j));
}
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
memset(fl,0,sizeof(fl));
if(s[i][j]=='.'&&!ma[id(i,j)]) {
dgs(id(i,j));
}
}
}
bool fll=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(ans[id(i,j)]) {
if(!fll) puts("WIN");
fll=1;
printf("%d %d\n",i,j);
}
}
}
if(!fll) puts("LOSE");
return 0;
}
例题7
Luogu P2172 [国家集训队]部落战争
先来证明：像马一样在网格图上跳跃形成的轨迹为二分图,即只存在偶环
Pf: 假设从\((0,0)\)开始，每次\(+-(a,b)\),\(+-(b,a),a>0,b>0\)
不妨设\(x(a,b)+y(b,a)=(0,0)\),则
\[\left\{
\begin{array}{c}
ax+by=0 \\
bx+ay=0
\end{array}
\right.
\] 相加发现：
\[(a+b)(x+y)=0
\] 则：
\[x+y=0
\] 所以只存在偶环
求最小不可重路径覆盖即可
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,m,r,c,ma[N];
bool fl[N];
char s[N][N];
vector<int>V[N];
inline int id(int x,int y) {
return (x-1)*m+y;
}
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main() {
scanf("%d%d%d%d",&n,&m,&r,&c);
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s[i][j]=='.'){
if(s[i+r][j+c]=='.') {
V[id(i,j)].push_back(id(i+r,j+c));
}
if(s[i+c][j+r]=='.'){
V[id(i,j)].push_back(id(i+c,j+r));
}
if(j-c>0&&s[i+r][j-c]=='.') {
V[id(i,j)].push_back(id(i+r,j-c));
}
if(j-r>0&&s[i+c][j-r]=='.'){
V[id(i,j)].push_back(id(i+c,j-r));
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) {
if(s[i][j]=='.') {
ans++;
memset(fl,0,sizeof(fl));
if(dfs(id(i,j))) ans--;
}
}
}
printf("%d\n",ans);
return 0;
}
例题8
幻灯片
建立二分图后判断是否可以有多解
法1：暴力删除边后判断答案是否相同
法2：对每条匹配边建反边（提供反悔机会），在残余网络上查找是否存在环，如果存在说明有多解
有向图判断具体的环，只能tarjan
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,ma[N],to[N],x[N],y[N],x1[N],t1[N],x2[N],y2[N],dfn[N],low[N],st[N],top,co[N],col,cnt;
bool fl[N];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
void tar(int u) {
dfn[u]=low[u]=++cnt; st[++top]=u;
for(auto v:V[u]) {
if(!dfn[v]) {
tar(v),low[u]=min(low[u],low[v]);
} else if(!co[v]) {
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]) {
co[u]=++col;
while(st[top]!=u) {
co[st[top]]=col; top--;
}
top--;
}
}
int main(){
scanf("%d",&n); int id=0;
while(n) {
printf("Heap %d\n",++id);
for(int i=1;i<=n;i++) {
scanf("%d%d%d%d",&x1[i],&x2[i],&t1[i],&y2[i]);
}
for(int i=1;i<=n;i++) {
scanf("%d%d",&x[i],&y[i]);
V[i].clear();
for(int j=1;j<=n;j++) {
if(x1[j]<x[i]&&x[i]<x2[j]&&t1[j]<y[i]&&y[i]<y2[j]) {
V[i].push_back(j);
}
}
}
memset(ma,0,sizeof(ma));
int ans=0;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans++;
}
/*if(ans!=n) {
puts("none");
} else */{
for(int i=1;i<=n+n;i++) {
V[i].clear();
}
for(int i=1;i<=n;i++) {
to[ma[i]]=i; V[i+n].push_back(ma[i]);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(to[i]!=j&&x1[j]<x[i]&&x[i]<x2[j]&&t1[j]<y[i]&&y[i]<y2[j]) {
V[i].push_back(j+n);
}
}
}
memset(dfn,0,sizeof(dfn));
memset(co,0,sizeof(co));
col=0; top=0; cnt=0;
for(int i=1;i<=n+n;i++) {
if(!dfn[i]) tar(i);
}
bool fll=0;
for(int i=1;i<=n;i++) {
if(co[ma[i]]!=co[i+n]) {
printf("(%c,%d) ",i+'A'-1,ma[i]);
fll=1;
}
}
if(!fll) {
puts("none");
} else puts("");
}
scanf("%d",&n);
}
return 0;
}
例题9
模板集合
只能有一个“*”,所以将所有可能的01子串处理出
将可能合并的子串用边相连，只会有一个位置不同，所以可以按01子串中1的个数的奇偶性分成二分图
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,m,ma[N];
bool fl[N],num[N],t[N];
char s[N];
vector<int>V[N];
inline int id(int x,int y) {
return (x-1)*m+y;
}
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main() {
scanf("%d%d",&m,&n);
for(int i=1;i<=1023;i++) {
num[i]=num[i>>1]^(i&1);
}
while(n||m) {
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++){
scanf("%s",s+1);
int t1=0,t2=-1;
for(int j=1;j<=m;j++) {
if(s[j]=='*') {
t1<<=1,t2=t1|1;
} else {
t1=(t1<<1)|(s[j]=='1');
if(t2!=-1) {
t2=(t2<<1)|(s[j]=='1');
}
}
}
t[t1]=1;
if(t2!=-1) t[t2]=1;
}
for(int i=1;i<=1023;i++) {
V[i].clear();
}
for(int i=0;i<=1023;i++){
if(t[i])
for(int j=1;j<=m;j++) {
if((i&(1<<j-1))==0) {
int k=i|(1<<j-1);
if(t[k]) {
if(num[i]) {
V[i].push_back(k);
} else {
V[k].push_back(i);
}
}
}
}
}
int ans=0;
memset(ma,0,sizeof(ma));
for(int i=0;i<=1023;i++){
if(t[i]) ans++;
if(t[i]&&num[i]) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans--;
}
}
printf("%d\n",ans);
scanf("%d%d",&m,&n);
}
return 0;
}
例题10
男孩女孩
求最大团
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,K,f[N][N],ma[N];
bool fl[N];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&m,&K); int id=0;
while(n||m||K) {
id++; printf("Case %d: ",id);
memset(f,0,sizeof(f));
for(int i=1;i<=K;i++) {
int u,v; scanf("%d%d",&u,&v);
f[u][v]=1;
}
for(int i=1;i<=n;i++) {
V[i].clear();
for(int j=1;j<=m;j++) {
if(!f[i][j]) {
V[i].push_back(j);
}
}
}
memset(ma,0,sizeof(ma));
int ans=n+m;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans--;
}
printf("%d\n",ans);
scanf("%d%d%d",&n,&m,&K);
}
return 0;
}
例题 11
Luogu P4298 [CTSC2008]祭祀
最长反链=最小可重路径覆盖
第一问，第二问，KO
第三问：将该点和其关的所有点删掉，如果该点可能成为祭点，则反链数量会减少1，再来一遍即可
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,f[N][N],ma[N];
bool fl[N],vis[N<<1],to[N],ban[N];
vector<int>V[N],V1[N];
bool dfs(int u) {
if(ban[u]) return 0;
for(auto v:V[u]) {
if(!ban[v]&&!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
void dgs(int u) {
vis[u]=1;
for(auto v:V[u]) {
if(!fl[v]){
fl[v]=1;
vis[v+n]=1;
dgs(ma[v]);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
int u,v; scanf("%d%d",&u,&v);
f[u][v]=1;
}
for(int k=1;k<=n;k++) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(f[i][k]&&f[k][j]) f[i][j]=1;
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(f[i][j]) {
V[i].push_back(j);
V1[j].push_back(i);
}
}
}
int ans=n;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans--;
}
printf("%d\n",ans);
for(int i=1;i<=n;i++) to[ma[i]]=1;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(!to[i]) dgs(i);
}
for(int i=1;i<=n;i++) {
printf("%d",vis[i]&(!vis[i+n]));
}
puts("");
for(int i=1;i<=n;i++) {
int res=n;
memset(ban,0,sizeof(ban));
for(int j=1;j<=n;j++) {
if(f[i][j]||f[j][i]||i==j) {
ban[j]=1;
res--;
}
}
memset(ma,0,sizeof(ma));
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) res--;
}
printf("%d",res==ans-1);
}
return 0;
}
例题12
Luogu P3231 [HNOI2013]消毒
考虑2维：对于\((a,b)\)的代价\(min(a,b)\)，可以看出消去\(a\)次行，或者消去\(b\)次列
所以可以将行列分开做，二分图
再加1维，没有三分图这种东西，发现最小的一维最大为17，所以暴力枚举最小一维怎么删的状态，将没被删的叠在一起，看作2维
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,ma[N],lim,a[N],b[N],c[N],fl[N];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(fl[v]!=lim) {
fl[v]=lim;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main(){
// freopen("1.in","r",stdin);
int T; scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&a[0],&b[0],&c[0]);
int ans=1e9; n=0;
for(int i=1;i<=a[0];i++) {
for(int j=1;j<=b[0];j++) {
for(int k=1;k<=c[0];k++) {
int op; scanf("%d",&op);
if(op) {
a[++n]=i,b[n]=j,c[n]=k;
}
}
}
}
if(a[0]>=b[0]&&b[0]<=c[0]) swap(a,b);
if(a[0]>=c[0]&&b[0]>=c[0]) swap(b,c);
for(int i=0;i<(1<<a[0]);i++) {
memset(fl,0,sizeof(fl));
memset(ma,0,sizeof(ma));
int res=0;
for(int j=1;j<=n;j++) {
if(!(i&(1<<a[j]-1))) V[b[j]].push_back(c[j]);
}
for(int j=1;j<=a[0];j++) {
if(i&(1<<j-1)) res++;
}
for(int j=1;j<=b[0];j++) {
lim=j;
if(dfs(j)) res++;
}
ans=min(ans,res);
for(int j=1;j<=n;j++) {
V[b[j]].clear();
}
}
printf("%d\n",ans);
}
return 0;
}
|
