2分匹配 从陌生到认知
参考 http://blog.csdn.net/q3498233/article/details/5786225
二分图：二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联的两个顶点恰好一个属于集合X，另一个属于集合Y。
二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
最大匹配：图中包含边数最多的匹配称为图的最大匹配。
完美匹配：如果所有点都在匹配边上，则称这个最大匹配是完美匹配。
二分图匹配基本概念：
未盖点
设VI是G的一个顶点，如果VI不与任意一条属于匹配M的边相关联，就称VI是一个未盖点。
交错轨
设P是图G的一条轨，如果P的任意两条相邻的边一定是一条属于M而另一条不属于M，就称P是交错轨。
可增广轨（增广路）
两个端点都是未盖点的交错轨称为可增广轨。
可增广轨的性质：
1：P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
2：P经过取反操作可以得到一个更大的匹配M’。
3：M为G的最大匹配当且仅当不存在相对于M的增广路径。
二分图最大匹配匈牙利算法：
算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"取反",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路。
代码：
模板
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
const int MAXN=11111;//根据点的个数变
int linker[MAXN];
bool used[MAXN];
vector<int>map[MAXN];
int uN;
bool dfs(int u)
{
for(int i=0;i<map[u].size();i++)
{
if(!used[map[u][i]])
{
used[map[u][i]]=true;
if(linker[map[u][i]]==-1||dfs(linker[map[u][i]]))
{
linker[map[u][i]]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int u;
int res=0;
memset(linker,-1,sizeof(linker));
for(u=0;u<uN;u++)
{
memset(used,false,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
int main()
{
int u,k,v,i;
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)//n个点 m条边
{
for( i=0;i<MAXN;i++)
map[i].clear();
for(i=0;i<m;i++)
{
scanf("%d %d",&v,&u);
v=v-1;//如果点是从1开始计数的 要减1 如果从0开始去掉这句以及下面那句
u=u-1;
map[u].push_back(v);
map[v].push_back(u);
}
uN=n;
printf("%d\n",hungary()/2);
}
return 0;
}
真正求二分图的最大匹配的题目很少，往往做一些简单的变化：
变种1：二分图的最小顶点覆盖
最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。
knoig定理:二分图的最小顶点覆盖数 = 二分图的最大匹配数（m）。
变种2：DAG图的最小路径覆盖
用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。
结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）
变种3:二分图的最大独立集
结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）
最大独立集相当于问：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值
当我们遇到的题目中可以将数据分成2个集合的时候就应该敏感性的想到二分匹配
最大独立集例题 ：
hdu 3829 二分图最大独立集
//Cat VS Dog.cpp : 定义控制台应用程序的入口点。
//
/*
题目描述：动物园有N只猫，M只狗，P个小孩。每个小孩都有自己喜欢的动物和讨厌的动物，如果他喜欢狗，那么就讨厌猫，
如果他讨厌猫，那么他就喜欢狗。某个小孩能开心，当且仅当他喜欢的动物留在动物园和讨厌的动物不在动物园里面。
现让管理员通过带走某些动物，问最多能使多少个孩子开心。
解题思路：题目有一个关键点，孩子喜欢猫，必然不喜欢狗，反之。 即猫和猫之间，狗和狗之间一定不存在矛盾关系，符合二分图的概念。
如何建立二分图：
若甲小孩喜欢的动物与乙小孩讨厌的动物一样，或者甲小孩讨厌的动物与乙小孩喜欢的动物一样，那甲乙之间就存在着排斥关系，则他们之间连接一条边。
建立完二分图之后，相当于求二分图的最大独立集 = 顶点数 - 最大匹配数。
*/
#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 508;
struct Child
{
string like;
string dis;
};
Child cat[MAXN],dog[MAXN];
int map[MAXN][MAXN];
int link[MAXN];
int used[MAXN];
int cat_num;
int dog_num;
int dfs(int k)
{
for(int i=0; i<dog_num; i++)
{
if(!used[i] && map[k][i])
{
used[i] = 1;
if(link[i] == -1 || dfs(link[i]))
{
link[i] = k;
return 1;
}
}
}
return 0;
}
int maxMatch()
{
int cnt = 0;
for(int i=0; i<cat_num; i++)
{
memset(used,0,sizeof(used));
if(dfs(i))
{
cnt++;
}
}
return cnt;
}
int main()
{
int n,m,p;
string a,b;
while(cin>>n>>m>>p)
{
memset(map,0,sizeof(map));
memset(link,-1,sizeof(link));
cat_num = dog_num = 0;
while(p--)
{
cin>>a>>b;
//将喜欢猫的孩子划为A子集
if(a[0] == 'C')
{
cat[cat_num].like = a;
cat[cat_num].dis = b;
cat_num++;
}
//将喜欢狗的孩子划为B子集
if(a[0] == 'D')
{
dog[dog_num].like = a;
dog[dog_num].dis = b;
dog_num++;
}
}
for(int i=0; i<cat_num; i++)
{
for(int j=0; j<dog_num; j++)
{
//若存在排斥关系
if(cat[i].like == dog[j].dis || cat[i].dis == dog[j].like)
{
map[i][j] = 1;
}
}
}
int cnt = maxMatch();
//最大独立集 = 顶点数 - 最大匹配数
cout<<cat_num+dog_num-cnt<<endl;
}
return 0;
}
HDU 1068 Girls and Boys（最大独立集） 参考 http://www.2cto.com/kf/201207/141366.html
/*
题意：n个同学，一些男女同学会有缘分成为情侣，格式ni:(m) n1 n2 n3表示同学ni有缘与n1,n2,n3成为情侣，求集合中不存在有缘成为情侣的同学的最大同学数。
题解：
独立集：图的顶点集的子集，其中任意两点不相邻
最大独立集 = 顶点数 - 最大匹配数
但是这道题有一点不同，它没有告诉我们是男生还是女生，所以我们需要进行拆点，把一个学生拆成一个男生和一个女生，然后求出最大匹配后除以2即可。
*/
#include <iostream>
using namespace std;
const int nMax = 500;
int n;
int map[nMax][nMax];
int link[nMax];
int useif[nMax];
bool can(int t)
{
for(int i = 0; i < n; ++ i)
{
if(!useif[i] && map[t][i])
{
useif[i] = 1;
if(link[i] == -1 || can(link[i]))
{
link[i] = t;
return 1;
}
}
}
return 0;
}
int main()
{
//freopen("f://data.in", "r", stdin);
while(scanf("%d", &n) != EOF)
{
memset(map, 0, sizeof(map));
memset(link, -1, sizeof(link));
int u, k, v;
for(int i = 0; i < n; ++ i)
{
scanf("%d: (%d)", &u, &k);
while(k --)
{
scanf("%d", &v);
map[u][v] = 1;
}
}
int num = 0;
for(int i = 0; i < n; ++ i)
{
memset(useif, 0, sizeof(useif));
if(can(i)) ++ num;
}
printf("%d\n", n - num / 2);
}
return 0;
}
最小路径覆盖
路径覆盖的定义是：在有向图中找一些路径，使之覆盖了图中的所有顶点，就是任意一个顶点都跟那些路径中的某一条相关联，且任何一个顶点有且只有一条路径与之关联，一个单独的顶点是一条路径.最小路径覆盖就是最少的路径覆盖
注意：每个点的入度出度都是1 也就是说 每个点决定1条边
poj 1422
题意：一个地图上有n个小镇，以及连接着其中两个小镇的有向边，而且这些边无法形成回路。现在选择一些小镇空降士兵（1个小镇最多1个士兵），士兵能沿着边走到尽头，问最少空降几个士兵，能遍历完所有的小镇。
思路：匈牙利算法求最小路径覆盖：在一个有向图中，路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m
用二分图来做
对于这样的一个有向图做最小路径覆盖，首先建图
先拆点，将每个点分为两个点，左边是1到n个点，右边是1-n个点
然后每一条有向边对应左边的点指向右边的点
这样建好图之后求最大匹配数
因为最小路径覆盖=点数-最大匹配数
/*
*/
#include<iostream>
using namespace std;
#define MAXV 130
int n,m; //交叉路口和街道的个数
int map[MAXV][MAXV];
int link[MAXV],use[MAXV];
bool dfs(int x){
int i,j;
for(i=1;i<=n;i++){
if(map[x][i] && !use[i] ){ //拆点注意i不能等于x，否则就自己和自己匹配了
j=link[i];
use[i]=1;
link[i]=x;
if(j==-1 || dfs(j)) return true;
link[i]=j;
}
}
return false;
}
int hungary(){
int num=0;
int i;
memset(link,-1,sizeof(link));
for(i=1;i<=n;i++){
memset(use,0,sizeof(use));
if(dfs(i)) num++;
}
return n-num;
}
int main(){
int Case;
int a,b,i;
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&m);
memset(map,0,sizeof(map));
for(i=0;i<m;i++){
scanf("%d%d",&a,&b);
map[a][b]=1;
}
printf("%d\n",hungary());
}
return 0;
}
/*题目大意：在一个坐标图中有一些点需要覆盖，每在一个点上覆盖就可在覆盖它上下左右4个点中任一个，问最小放几个。
分析：利用黑白染色法把每一个点都和与之相邻的4个点连边，就构成了一个二分图。要求的就是有最小的点数覆盖全部边，即求最小路径覆盖=最大独立集=所有点-最大匹配由此可以求出最优解。实现方法——匈牙利算法即可。注意的是，这里的点是所有可以放得点*2，而匹配数也是正常匹配数的二倍（A到B连了，B到A也连了），所以最后是n-最大匹配/2。
代码：
*/
#include<iostream>
using namespace std;
int h[41][11];
int g[405][405],visit[405],match[405];
char map[41][11];
int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,m,ans,sum;
int find(int a)
{
int i,j;
for(i=1;i<=sum;i++)
{
if(!visit[i]&&g[a][i]==1)
{
visit[i]=1;
if(match[i]==0||find(match[i]))
{
match[i]=a;
return 1;
}
}
}
return 0;
}
int main()
{
int t,i,j,k,xx,yy;
cin>>t;
while(t--)
{
sum=ans=0;
memset(g,0,sizeof(g));
memset(match,0,sizeof(match));
cin>>n>>m;
for(i=0;i<n;i++)
{
cin>>map[i];
for(j=0;j<m;j++)
{
if(map[i][j]=='*')
{
sum++;
h[i][j]=sum;
}
}
}
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(map[i][j]=='*')
{
for(k=0;k<=3;k++)
{
xx=i+d[k][0];
yy=j+d[k][1];
if(xx>=0&&yy>=0&&xx<n&&yy<m&&map[xx][yy]=='*')
g[h[i][j]][h[xx][yy]]=1;
}
}
}
for(i=1;i<=sum;i++)
{
memset(visit,0,sizeof(visit));
if(find(i)) ans++;
}
cout<<sum-ans/2<<endl;
}
return 0;
}