二分图
染色法判断二分图
- 不含奇数环等价于染色法过程不存在矛盾
cpp
bool dfs(int u,int c){
col[u]=c;
for(auto v:adj[u]){
if(col[v]){
if(col[v]==c)return false;
}
else if(!dfs(v,3-c))return false;
}
return true;
}匈牙利算法
cpp
int st[N],timestamp;//表示当轮是否被匹配过，bool改用时间戳
int match[N];//表示匹配的对象
bool find(int u){
for(auto v:adj[u]){
if(st[v]!=timestamp){
st[v]=timestamp;
if(match[v]==0||find(match[v])){
//没被匹配或者找到对应的增广路
match[v]=u;
return true;
}
}
}
return false;
}
int main(){
int res=0;
for(int i=1;i<=n;i++){
timestamp++;
if(find(i))res++;
}
cout<<res<<"\n";
return 0;
}UVA1194 Machine Schedule
题意：
n个任务，A机器有n种模式，B机器有m种模式，每个任务可以被A或B的一种模式完成
切换任务需要重启机器，求最少重启次数
思路：
- 排除可以用0模式的，因为可以放到一开始全部做完
- A的模式向B的模式连边
- 题意即求最小点覆盖，即每条边至少有一个点被选
cpp
int g[N][N],match[N],n,m,k;
bool st[N];
bool find(int u){
for(int v=1;v<m;v++){
if(!st[v]&&g[u][v]){
st[v]=1;
int t=match[v];
if(t==0||find(t)){
match[v]=u;
return true;
}
}
}
return false;
}
void solve(){
while(cin>>n,n){
memset(match,0,sizeof match);
memset(g,0,sizeof g);
cin>>m>>k;
int t;
while(k--){
int t,a,b;
cin>>t>>a>>b;
if(!a||!b)continue;
g[a][b]=1;
}
int res=0;
for(int i=1;i<n;i++){
memset(st,0,sizeof st);
if(find(i))res++;
}
cout<<res<<"\n";
}
}P6062 [USACO05JAN] Muddy Fields G
题意：
给定n*m的矩形，每个方格代表草地和泥地
可以使用宽度为1的任意长度木板覆盖泥地，木板可以重复覆盖，求最少木板
思路：
横着放的木板为左端点，竖着放的为右端点，对每个泥地，横竖连边
即求最小权点覆盖
cpp
int idx,n,m;
vector<int> adj[N];
bool st[N];
int match[N];
char a[60][60];
int r[60][60];
bool find(int u){
for(auto v:adj[u]){
if(!st[v]){
st[v]=1;
int t=match[v];
if(t==0||find(t)){
match[v]=u;
return true;
}
}
}
return false;
}
void solve(){
map<int,int> mp;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)cin>>a[i][j];
for(int j=1;j<=m;j++){
if(a[i][j]=='*'){
if(j==1||a[i][j-1]=='.')r[i][j]=++idx;
else r[i][j]=idx;
}
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(a[i][j]=='*'){
if(i==1||a[i-1][j]=='.')++idx;
adj[r[i][j]].push_back(idx);
}
}
}
int res=0;
for(int i=1;i<=idx;i++){
memset(st,0,sizeof st);
if(find(i))res++;
}
cout<<res<<"\n";
}P1129 [ZJOI2007] 矩阵游戏
题意：
给定01矩阵，可以进行两种操作
每次可以交换行和列
求是否可以使得主对角线上全是1
思路：
- 行向列连边，如果二分图最大匹配res==n那么就可以
- 每一行列都至少有一个匹配，交换行列不会影响匹配性
cpp
int match[N];
bool st[N];
vector<int> adj[N];
int g[N][N];
bool find(int u){
for(auto v:adj[u]){
if(!st[v]){
st[v]=1;
int t=match[v];
if(t==0||find(t)){
match[v]=u;
return true;
}
}
}
return false;
}
void solve(){
int n;
cin>>n;
memset(match,0,sizeof match);
for(int i=1;i<=2*n;i++)adj[i].clear();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>g[i][j];
if(g[i][j]==1){
adj[i].push_back(n+j);
}
}
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=n+1;j<=2*n;j++)st[j]=0;
res+=find(i);
}
cout<<(res==n?"Yes\n":"No\n");
}P1640 [SCOI2010] 连续攻击游戏
题意：
一个装备有2种属性，且只能使用其中一种属性
i从1开始，每次可以使用属性为i的一个装备攻击
求最多能连续攻击多少下
思路：
- 一个装备匹配一个属性，使用二分图
- 遇到增广失败的属性，直接break
- 小技巧：使用时间戳代替memset st
cpp
int match[N],now;
int st[N];
vector<int> adj[N];
bool find(int u){
for(auto v:adj[u]){
if(st[v]!=now){
st[v]=now;
int t=match[v];
if(t==0||find(t)){
match[v]=u;
return true;
}
}
}
return false;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
adj[x].push_back(i+10000);
adj[y].push_back(i+10000);
}
int res=0;
for(int i=1;i<=10000;i++){
now=i;
if(find(i))res++;
else break;
}
cout<<res<<"\n";
}相关应用
- 最大匹配数=最小点覆盖=总点数-最大独立集=总点数-最小路径点覆盖(最小路径重复点覆盖)
最小点覆盖：每条边都有一个点被选
- 最小权点覆盖>=最大匹配数
- 证明等号成立。
- 构造方案：
- 从左边所有非匹配点出发，跑一遍增广，标记路径上的点
- 左边所有未被标记的点和右边所有标记的点组成一种方案
- 左边非匹配点一定被标记，右边非匹配点一定不被标记
- 对于匹配边，要么同时被标记，要么同时不被标记
- 左边非匹配点->右边匹配点，右边匹配点一定被标记，右边会被选择
- 左边匹配点->右边非匹配点，左边匹配点一定不被标记，左边点会被选择
最大独立集：选出最多的点集，使得内部没有边
- 最大独立集=选最少的点将图破坏掉=最小点覆盖
最小路径点覆盖：用最少的互不相交的路径将点覆盖
针对DAG(有向无环图)
- 拆点，如果一条路径i->j，那么i的出点连向j的入点
- 对于路径终点，其没有出边，因此为左部的非匹配点
- 即让左部非匹配点尽可能少，左部匹配点尽可能多，记为m,答案即n-m
最小路径重复点覆盖：路径可以相交
- 求传递闭包，获得图G'
- 原图的最小路径重复点覆盖=新图最小路径点覆盖
acwing379 捉迷藏
题意：
给定一张有向无环图，如果a能沿一条路径走到b那么a和b是能相互看见的
玩家1要选择k个藏身点，玩家2要找这k个藏身点
需要保证藏身点之间互不可达，问最多能选多少个藏身点
思路：
答案k=最小路径重复点覆盖cnt
- 首先对于每条路径最多只能选一个点，即cnt>=k
- 然后证明:cnt=k
- 构造一种方法，选择每条路径的终点e
- 设终点集合为E，终点能到的点为next(E)
- 如果两个集合交集为空，说明终点不能被任意点到达，答案即为k=cnt
- 两个集合不为空，对于能被其他点到达的终点ei，一直往回退，直至交集为空
- 证明一定可以找到这样的点ei：
- 如果找不到，那么整条路径都可以被其他点到达，那么其他店连上起点就会将两条路合并成一条，与最小路径覆盖矛盾
cpp
int g[N][N],match[N],n,m;
bool st[N];
bool find(int u){
for(int i=1;i<=n;i++){
if(g[u][i]&&!st[i]){
st[i]=1;
int t=match[i];
if(t==0||find(t)){
match[i]=u;
return true;
}
}
}
return false;
}
void solve(){
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
g[a][b]=1;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)g[i][j]|=g[i][k]&g[k][j];
}
}
int res=0;
for(int i=1;i<=n;i++){
memset(st,0,sizeof st);
if(find(i))res++;
}
cout<<n-res<<"\n";
}