二分图总结
模版
hungary
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| int g[maxn][maxn],linker[maxn]; bool used[maxn]; bool dfs(int u){ for(int i=0;i<m;i++){ if(g[u][i] && !used[i]){ used[i]=true; if(linker[i]==-1 || dfs(linker[i])){ linker[i]=u; return true; } } } return false; } int hungary(){ int ans=0; mm(linker,-1); for(int i=0;i<n;i++){ mm(used,0); if(dfs(i)) ans++; } return ans; }
|
下标从0开始 n和m分别记录2个集合的点数
km
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| int nx,ny; int g[maxn][maxn]; int linker[maxn],lx[maxn],ly[maxn]; int slack[maxn]; bool visx[maxn],visy[maxn]; bool dfs(int x){ visx[x]=true; for(int y=0;y<ny;y++){ if(visy[y]) continue; int tmp=lx[x]+ly[y]-g[x][y]; if(tmp==0){ visy[y]=true; if(linker[y]==-1 || dfs(linker[y])){ linker[y]=x; return true; } } else slack[y]=min(slack[y],tmp); } return false; } int km(){ mm(linker,-1),mm(ly,0); for(int i=0;i<nx;i++){ lx[i]=g[i][0]; for(int j=1;j<ny;j++) lx[i]=max(lx[i],g[i][j]); } for(int i=0;i<nx;i++){ fill(slack,slack+ny,inf); while(1){ mm(visx,false),mm(visy,false); if(dfs(i)) break; int d=inf; for(int j=0;j<ny;j++){ if(!visy[j]) d=min(d,slack[j]); } for(int j=0;j<nx;j++){ if(visx[j]) lx[j]-=d; } for(int j=0;j<ny;j++){ if(visy[j]) ly[j]+=d; else slack[j]-=d; } } } int ans=0; for(int i=0;i<ny;i++){ if(linker[i]!=-1) ans+=g[linker[i]][i]; } return ans; }
|
下标从0开始 nx和ny分别记录2个集合的点数
相关结论
二分图判定
dfs交叉染色法
转跳链接
最小边覆盖
最小边覆盖 = 最大独立集 = 顶点数 - 最大匹配数
这是二分图的基本性质 需要满足原图是二分图
这里的最大匹配数是在原二分图上进行的
最大匹配用匈牙利算法
最小路径覆盖
最小路径覆盖=顶点数-最大匹配数
最小路径覆盖和最小边覆盖不同,不要求给的图是二分图,而是要求是有向图,不能有环,然后根据原图构造二分图
构造方法是拆点 最大匹配用dinic 转跳链接
也可以用匈牙利求匹配
最小顶点覆盖
最小顶点覆盖=最大匹配数
要求原图是二分图 使用匈牙利算法
最大带权独立集合
最大带权独立集合=总权值-最小顶点覆盖=总权值-最大匹配数
拆点 用dinic求最大匹配数
转跳链接
带权最小k路径覆盖
网络流
转跳链接
最大团
最大团顶点数 = 原图补图的最大独立集顶点数 = 补图顶点数-补图最大匹配数
最大匹配数用匈牙利算法
uva 12549
题目要求
紫书P381
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
| using namespace std; int t,r,c,n,m,num; int mp[maxn][maxn]; int g[maxn][maxn],linker[maxn]; bool used[maxn]; struct node{ int x,y; }a[maxn][maxn]; bool dfs(int u){ for(int i=0;i<m;i++){ if(g[u][i] && !used[i]){ used[i]=true; if(linker[i]==-1 || dfs(linker[i])){ linker[i]=u; return true; } } } return false; } int hungary(){ int ans=0; mm(linker,-1); for(int i=0;i<n;i++){ mm(used,0); if(dfs(i)) ans++; } return ans; } void build(){ int row=-1,col=-1; for(int i=1;i<=r;i++){ bool flag=true; for(int j=1;j<=c;j++){ if(mp[i][j]==1){ if(flag) row++; a[i][j].x=row; flag=false; } if(mp[i][j]==2) flag=true; } } for(int j=1;j<=c;j++){ bool flag=true; for(int i=1;i<=r;i++){ if(mp[i][j]==1){ if(flag) col++; a[i][j].y=col; flag=false; } if(mp[i][j]==2) flag=true; } } n=row+1,m=col+1; for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ if(mp[i][j]==1) g[a[i][j].x][a[i][j].y]=1; } } } int main(){ // freopen("input.txt","r",stdin); scanf("%d",&t); while(t--){ mm(mp,0),mm(g,0),mm(a,0); scanf("%d%d",&r,&c); scanf("%d",&num); while(num--){ int x,y; scanf("%d%d",&x,&y); mp[x][y]=1; //重要 } scanf("%d",&num); while(num--){ int x,y; scanf("%d%d",&x,&y); mp[x][y]=2; //障碍 } build(); printf("%d\n",hungary()); } return 0; }
|
思路
本题可以转换为最小顶点覆盖 二分图的最小顶点覆盖=二分图最大匹配数
重在建图(若没有障碍更简单 有障碍只需要领取一行或一列即可) 然后直接跑hungary即可
初始化row和col为-1 遇到重要位置记录下行或者列 若遇到障碍物 行和列需要额外加1 代表需要新的机器人
row是从行开始 col是从列开始 n和m更新2个集合的点数
最后的二分图相当于:第一个集合代表行 第二个集合代表列 某个机器人可以守护某一行或者某一列 对应的行列相连
最小顶点覆盖即为选择最少的机器人能够守护到所有的行或列
HDU 1150
转跳链接
HDU 2255
转跳链接
HDU 1533
转跳链接