一.最大匹配：
匈牙利算法：
总体来说，就是不断找增广路，如果找到 i 可以匹配而没有匹配的点 j ，就将这个点 j 与 i 配对，而如果发现要匹配的点 j 已经和 k 配对了，就对这个点 j 所配对的点 k 进行寻找增广路的操作，看这个点k 能不能另外找到其他的点 x 来替代 j 点来进行配对,如果可以，就用 x来代替 j 和k 进行配对，j 和 i来配对，即可。如果找不到，那么就用另外的点来和 i 进行配对尝试。以此类推。
匈牙利算法建的是单向边
代码1：（建双向边）：
#include <bits/stdc++.h>
using namespace std;//不断妥协,不断找增广路
const int N=1e3+5;
vector<int>pic[N];//邻接表存图
int match[N];//所匹配的顶点
bool vis[N];//dfs的访问标记
int k,n,m;
void add_edge(int u,int v)
{
pic[u].push_back(v);
pic[v].push_back(u);
}
bool dfs(int v)//dfs找增广路
{
vis[v]=true;
for(int i=0;i<pic[v].size();i++)
{
int u=pic[v][i];
int w=match[u];
if(w<0||!vis[w]&&dfs(w))//要被配对的点，要么还没有配对，要么已经配对，但可以妥协（让和它配对的与能够配对的配对）
{//匈牙利树，交替路，稀疏图bfs更快，稠密图接近
match[v]=u;
match[u]=v;
return true;
}
}
return false;
}
//求解二分图的最大匹配
int b_matching()
{
int res=0;
memset(match,-1,sizeof(match));
for(int i=1;i<=m+n;i++)
{
if(match[i]<0)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
res++;
}
}
return res;
}
int main()
{
while(scanf("%d",&k),k)
{
scanf("%d%d",&m,&n);//女生1~m,男生m+1~m+n
int a,b;
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
add_edge(a,b+m);
}
printf("%d\n",b_matching());
}
return 0;
}
代码2：（HDU 2063）
当把点分成两份进行匹配，只遍历一边时，建单向边。
如果不分图，遍历全部点时，要建立双向边，最后最大匹配结果要除2
匈牙利算法模板，建有向边。
#include<cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=1100;
int k,n,m,V;
int match[N];
bool vis[N];
vector<int>pic[N];
bool dfs(int u)
{
for(int i=0;i<pic[u].size();i++)
{
int v=pic[u][i];
if(!vis[v])//走未匹配的边
{
vis[v]=true;
int w=match[v];
if(w<0||dfs(w))//dfs(w):走已匹配的边
{
match[v]=u;
return true;
}
}
}
return false;
}
int b_match()
{
int ans=0;
memset(match,-1,sizeof(match));
for(int i=1;i<=V;i++)
{
memset(vis,false,sizeof(vis));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
while(scanf("%d",&k),k)
{
scanf("%d%d",&m,&n);
V=n+m;
for(int i=1;i<=V;i++)
pic[i].clear();
int a,b;
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
pic[a].push_back(b+m);
}
printf("%d\n",b_match());
}
return 0;
}
二.最小顶点覆盖：
即用最少的点去覆盖所有的边。
先引入一个定理：
könig定理：最小顶点覆盖=最大匹配
因此求最小顶点覆盖就可以转化为求最大匹配，直接用模板就行。难点在于如何建立最小顶点覆盖的模型，常见的建图方法有行列建图（目前就遇见过这种），但根本在于如何根据问题性质去转化，找到对应的匹配关系，一般是通过目标把两个集合联系起来，建立匹配关系。
大致过程如下：
1.从右边找到一个未被匹配的点，标记。
2.走一条没被匹配的边，到左边的点，标记。
3.走一条匹配过的边到右边，标记。
4.重复2.3步骤直到不能再走。
5.回到步骤1，直到找不到未被匹配且未被标记的右边的点。
6.标记结束后，右边没有标记的点，和左边已经标记的点，就可以覆盖所有的边。
相关题目：*
POJ 3041 POJ 2446 POJ1486 POJ 1325 POJ 3020 HDU 1054
POJ 2226（巧妙建图）UVA 11419(*)
交替路：
从一个未匹配的点出发，依次经过非匹配边，匹配边，非匹配边，匹配边…形成的路径。
增广路：
从一个未匹配的点出发，走交替路，如果途径一个未匹配的点，（出发点不算），那么，这条路就叫做增广路。特点：非匹配边=匹配边+1
匈牙利算法就是走增广路，直到没有。
匈牙利树：
三.最小路径覆盖：
DAG图中（有向无环图）：
最小路径覆盖=顶点数-最大匹配
不可相交的最小路径覆盖：
代码（HDU 1151）：
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=130;
int n,m;
vector<int>pic[N];
int match[N];
bool vis[N];
bool dfs(int u)
{
for(int i=0;i<pic[u].size();i++)
{
int v=pic[u][i];
if(!vis[v])
{
vis[v]=true;
int w=match[v];
if(w<0||dfs(w))
{
match[v]=u;//存每个终点对应的起点
//match[u]=v;
return true;
}
}
}
return false;
}
int b_match()
{
int ans=0;
memset(match,-1,sizeof(match));
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
pic[i].clear();
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
pic[a].push_back(b);
}
printf("%d\n",n-b_match());
//for(int i=1;i<=n;i++)printf("%d:%d\n",i,match[i]);
}
return 0;
}
相关题目：
HDU 3335（最大独立集）
HDU 6311（*最小路径覆盖+路径输出）
HDU 4160
UVA 11419
POJ 2594（可相交的最小路径覆盖）
可相交的最小路径覆盖问题：
允许点重复走，即两点之间可以间接到达，不能直接建图跑二分图匹配。先用 floyd 求传递闭包，把间接到达改成直接到达，然后根据得到的邻接矩阵来建图。
最小路径覆盖=顶点数-最大二分匹配
*四.*最大独立集和最大团：
详解+模板
独立集：图中互不相连的顶点集合
最大独立集+最小顶点覆盖=顶点数
可以通过最大匹配求出最大独立集的数目
求最大独立集是一个NP难问题，目前没有多项式时间内的解法，所以常见解法就是搜索。
如果仅仅要求求出最大独立集的元素个数，可以直接用最大独立集和最大匹配的关系，跑一遍匈牙利算法即可。
如果要求输出最大独立集的元素，则要转化为最大团的问题，一个图的最大团=补图的最大独立集。
*五.最小边覆盖
无孤立点的图中，最大匹配+最小边覆盖=顶点数
完备匹配：
最佳匹配；
最佳完备匹配
多重匹配：
可以用网络流写
带权匹配：
可以用费用流
**二分图的最佳完备匹配（**KM算法）：
HDU 2255（用最大流最大费用可以解决）
京公网安备 11010502036488号