爵士OIer查看:0 回复:1 评论:0 创建时间:2020-05-04T15:25:00用户:爵士OIer查看:0 回复:1 评论:0 创建时间:2020-05-04T15:25:00
二分图
如图，一个图的点集可以划分为两个不相交的子集，每一个子集中的点和该子集中的其他点没有边相连的图就叫二分图。比如上面有两个点集u,v符合上述条件，则它是一个二分图。
二分图的判定
· 定理：一个无向图是二分图，当且仅当图中不存在奇环（长度为奇数的环）
· 根据该定理，可用染色法判定二分图：尝试用黑、白两种颜色标记图中的节点，当一个节点被标记后，它的所有邻接点应被标记为与它相反的颜色。若发生冲突，说明图中存在奇环。二分图染色一般基于DFS实现，时间复杂度为O(N+M)。
· 判定流程伪代码如下：
void dfs(int x,int color){
v[x]=color; //对点x染色
//遍历x相连的无向边(x,y)
if (v[y]==0) //未染色
dfs(y,3-color); //黑1，白2，3相减取反色
else if (v[y]==color)
//该无向图不是二分图，算法结束
//是无向图，算法结束
}
//在主函数中
for (int i=1;i<=n;i++)
if (v[i]==0) dfs(i,1);
二分图匹配
· 【任意两条边都没有公共端点】的边的集合称为图的匹配。
· 最大匹配（maximal matching problem)就是包含边的个数最多的匹配。
上面是一种匹配方式，但是不一定是最大匹配。
二分图匹配的用途很多，如自来水管、车站打车等。
增广路
· 对于任意一组匹配M（M是一个边集），属于M的边被称为“匹配边”，不属于M的边被称为“非匹配边”。
· 匹配边的端点被称为M的“饱和点”，其它节点被称为“非饱和点”
· p是G的一条通路，如果p中的边为属于M中的匹配边与不属于M的非匹配边交替出现，则称p是一条M-交错路。
· p是一条M-交错路，如果p的起点和终点都是非M-饱和点，则称p为M-增广路。
如上两图，左图是一种匹配。右图是一种更大的匹配。
· 增广路显然具有以下性质
1.长度len是奇数
2.路径上第1，3，5，……，len条边是非匹配边，第2，4，6，……，len-1条边是匹配边。
· 如果将增广路p上所有边的状态取反，即原来的边变为非匹配边，原来的非匹配边变成匹配边。那么新得到的边集M’仍然是一组匹配，并且匹配边数增加了1。由此可得推论：
· 二分图的一组匹配M是最大匹配，当且仅当图中不存在M的增广路。
匈牙利算法（增广路算法）
· 匈牙利算法，又称增广路算法，用于计算二分图最大匹配。其主要过程为：
1.设M为空集，即所有边都是非匹配边。
2.寻找M的增广路p，把路径上的所有边的匹配状态取反，得到一个更大的匹配M’。
3.重复第2步，直至图中不存在M的增广路。
· 该算法的关键在于如何找到一条增广路：依次尝试给每一个左部节点x寻找一个匹配的右部节点y。右部点y能与左部点x匹配：需要满足以下两个条件之一：
1.y本身就是非匹配点
此时无向边(x,y)本身就是非匹配边，自己构成一条长度为1的增广路。
2.y已经与左部点x’匹配，但从x’出发能找到另一个右部点y’与之匹配。
递归进入该左部点，为其寻找匹配的右部点，此时路径x~y~x’~y’为一条增广路。
· 在实际的程序实现中，可采用DFS的框架，递归地从x出发寻找增广路。若找到，则在深搜回溯时，正好把路径上的匹配状态取反。另外可以用全局bool数组标记节点的访问情况，避免重复搜索。
下面贴出具体流程，方便理解。
图一到图五很好理解，不讲；
可以看到，在图六中出现了两条红色的边。搜索到第四个白色点时，出现了下面这条红色的边，占用第三个黑色点。因此，第二个白色点重新建边，搜索与第二个白色点相邻的黑色点，搜索到了第一个黑色点，出现上面这条红色的边，发现这个黑色点如果被占用，那么第一个白色点将会无法建边，回溯；
到图七，第二个白色点搜索与没有被占用且与其联通的第四个黑色点，建边（图七中新出现的红色边），形成增广路。
至此，DFS过程结束。形成图八那样的一种从第一个白色点出发的最大匹配。
· 匈牙利算法的正确性基于贪心策略，它的一个重要特点是：当一个节点称为匹配点后，至多因为找到增广路而更换匹配对象，但是绝不会再变回非匹配点。
· 对于每个左部节点，寻找增广路最多遍历整张二分图一次。因此，该算法的时间复杂度为O(NM）。
Code：
bool dfs(int x){
int i,y;
for(i=head[x]; i>0; i=next[i]) //考虑与x相连的每个点y=ver[i]
if(!visit[y=ver[i]]){//没有被搜索过
visit[y]=1;
if(!match[y] || dfs(match[y])){
match[y]=x; return true;
}
}
return false;
}
//下面是主函数核心部分
for(int i=1;i<=n;i++){
memset(visit,0,sizeof(visit)); //清空访问标记
if(dfs(i)) ans++; //从左部点i出发寻找增广路
}
二分图匹配的模型
· 二分图匹配的模型有两个要素
1.节点能分成两个独立的集合，每个集合内部有0条边。
2.每个节点只能与1条匹配边相连。
例题：匈牙利算法-棋盘上的问题
还记得开篇的n皇后和状压DP吗？
棋盘覆盖
问题描述
给定一个N行N列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
输入格式
第一行包含两个整数N和t，其中t为禁止放置的格子的数量。
接下来t行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。
输出格式
输出一个整数，表示结果。
数据范围
1≤N≤100
输入样例
8 0
输出样例
32
相信大家一看到就以为是状压DP吧（雾
我们怎么用二分图的匈牙利算法？看下：
棋盘黑白染色
相邻格子连边
1*2骨牌对应一条匹配边
这个用特殊字体区分的就是简单思路。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 105
#define M 1000005
using namespace std;
struct E{int next,to;}e[M];
int n,m,num,ans;
int h[N*N],mat[N*N];
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
bool vis[N*N];
bool tag[N][N];
void add(int u,int v){
e[++num].next=h[u];
e[num].to=v;
h[u]=num;
}
int cal(int x,int y){return(x-1)*n+y;}
bool dfs(int x){
for(int i=h[x];i!=0;i=e[i].next)
if(!vis[e[i].to]){
vis[e[i].to]=1;
if(!mat[e[i].to]||dfs(mat[e[i].to])){
mat[e[i].to]=x;
return 1;
}
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
tag[x][y]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=4;k++){
int x=i,y=j;
int xx=x+dx[k],yy=y+dy[k];
if(xx<1||xx>n||yy<1||yy>n)continue;
if(tag[x][y]||tag[xx][yy])continue;
add(cal(x,y),cal(xx,yy));
add(cal(xx,yy),cal(x,y));
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((i+j)%2){
memset(vis,0,sizeof(vis));
if(dfs(cal(i,j)))ans++;
}
cout<<ans;
return 0;
}
巨的放置
题目描述
给定一个N行M列的棋盘，已知某些格子禁止放置。
问棋盘上最多能放多少个不能互相攻击的車。
車放在格子里，攻击范围与中国象棋的“車”一致。
输入格式
第一行包含三个整数N,M,T，其中T表示禁止放置的格子的数量。
接下来T行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。
输出格式
输出一个整数，表示结果。
数据范围
1≤N,M≤200
输入样例
8 8 0
输出样例
8
每行每列只能放一个車——所有行、所有列看做两组点某个格子可以放車——格子对应的行、列之间连边放置的車不能互相攻击——选择一组匹配#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
int n,m,t;
const int N=100000;
int head[N],nex[N],to[N],cnt;
bool g[220][220];
int match[N];
bool vis[N];
void init(){
mem(head,-1);
mem(nex,-1);
mem(to,-1);
cnt=0;
mem(match,-1);
mem(vis,false);
mem(g,true);
}
void add(int a,int b){
++cnt;
nex[cnt]=head[a];
head[a]=cnt;
to[cnt]=b;
}
bool dfs(int p){
for (int i=head[p];i!=-1;i=nex[i]){
int y=to[i];
if(vis[y])continue;
vis[y]=true;
if (match[y]==-1||dfs(match[y])){
match[y]=p;
return true;
}
}
return false;
}
int main(){
init();
cin >>n>>m>>t;
while(t--){
int x,y;
cin>>x>>y;
g[x][y]=false;
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (g[i][j]){
add(i,j+n);
add(j+n,i);
}
}
}
int res=0;
for (int i=1;i<=n;i++){
mem(vis,false);
if(dfs(i))res++;
}
cout<<res<<"\n";
return 0;
}
例题：Place the Robots
问题描述
有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、喵地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。
把每一行、每一列被墙隔开，并且包含空地的连续区域称作“块”。
显然，在一个块之中，最多只能放一个机器人。把这些块编上号。
把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。
由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。
