这个本来应该是在大一就掌握的算法，硬生生被我拖到现在。。。
匈牙利算法是用来求二分图的最大匹配的一种比较简单的算法，最核心的东西就是找增广路径。详情： http://blog.csdn.net/acdreamers/article/details/8621130
记住一些常见的结论：
(1)二分图的最小顶点覆盖
最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。
Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。
(2)DAG图的最小路径覆盖
用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。
结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）
(3)二分图的最大独立集
最大独立集问题： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值
结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）
匈牙利算法模板：
bool dfs(int x) {
for(int j=0; j<n; j++) {
if( Map[x][j] && !vis[j] ) {
vis[j] = true;
if( link[j]==-1 || dfs(link[j]) ) {
link[j] = x;
return true;
}
}
}
return false;
}
void solve() {
int res = 0;
CLS(link, -1);
for(int i=0; i<n; i++) {
CLS(vis, false);
if( dfs(i) ) res ++;
}
//这个res便是最大匹配数
}
再加几个模板题吧！ http://acm.hdu.edu.cn/showproblem.php?pid=1150
这个是求最小顶点覆盖~
// Asimple
#include <bits/stdc++.h>
#define INF 0xffffff
#define mod 1000000
#define swap(a, b, t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug( a ) cout << #a << " = " << a <<endl
#define abs(x) x<0?-x:x
#define srd(a) scanf("%d", &a)
#define src(a) scanf("%c", &a)
#define srs(a) scanf("%s", a)
#define srdd(a, b) scanf("%d %d",&a, &b)
#define srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
#define prd(a) printf("%d\n", a)
#define prdd(a, b) printf("%d %d\n",a, b)
using namespace std;
typedef long long ll;
const int maxn = 1005 ;
int n, m, num, T, k, x, y, len, ans;
int endx, endy, t;
int Map[maxn][maxn];
bool vis[maxn];
int link[maxn];
bool dfs( int x) {
for ( int j= 0 ; j<m; j++ ) {
if ( Map[x][j] && ! vis[j] ) {
vis[j] = true ;
if ( link[j]==- 1 || dfs(link[j]) ) {
link[j] = x;
return true ;
}
}
}
return false ;
}
void solve() {
int res = 0 ;
CLS(link, - 1 );
for ( int i= 0 ; i<n; i++ ) {
CLS(vis, false );
if ( dfs(i) ) res ++ ;
}
prd(res);
}
void input() {
while ( ~srd(n) && n ) {
srdd(m, num);
memset(Map, 0 , sizeof (Map));
for ( int i= 0 ; i<num; i++ ) {
srddd(x, x, y);
if ( x&&y ) Map[x][y] = 1 ;
}
solve();
}
}
int main(){
input();
return 0 ;
}
第二个： http://acm.hdu.edu.cn/showproblem.php?pid=1068
求最小路径覆盖数。由于本题是双向图，所以最小 路径覆盖数 等于顶点数n双向图的最大匹配/2
// Asimple
#include <bits/stdc++.h>
#define INF 0xffffff
#define mod 1000000
#define swap(a, b, t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug( a ) cout << #a << " = " << a <<endl
#define abs(x) x<0?-x:x
#define srd(a) scanf("%d", &a)
#define src(a) scanf("%c", &a)
#define srs(a) scanf("%s", a)
#define srdd(a, b) scanf("%d %d",&a, &b)
#define srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
#define prd(a) printf("%d\n", a)
#define prdd(a, b) printf("%d %d\n",a, b)
using namespace std;
typedef long long ll;
const int maxn = 1005 ;
int n, m, num, T, k, x, y, len, ans;
int Map[maxn][maxn];
bool vis[maxn];
int link[maxn];
bool dfs( int x) {
for ( int j= 0 ; j<n; j++ ) {
if ( Map[x][j] && ! vis[j] ) {
vis[j] = true ;
if ( link[j]==- 1 || dfs(link[j]) ) {
link[j] = x;
return true ;
}
}
}
return false ;
}
void solve() {
int res = 0 ;
CLS(link, - 1 );
for ( int i= 0 ; i<n; i++ ) {
CLS(vis, false );
if ( dfs(i) ) res ++ ;
}
prd(n -res/ 2 );
}
void input() {
while ( ~ srd(n) ) {
memset(Map, 0 , sizeof (Map));
for ( int i= 0 ; i<n; i++ ) {
scanf( " %d: (%d) " , &x, & num);
for ( int j= 0 ; j<num; j++ ) {
srd(y);
Map[x][y] = 1 ;
}
}
solve();
}
}
int main(){
input();
return 0 ;
}
再贴一个题。。 http://acm.hdu.edu.cn/showproblem.php?pid=1054
但是，很尴尬的是，我不用vector竟然时间超限。。蒙~~~
求最小顶点覆盖。由于本题是双向图，所以最小顶点覆盖等于双向图的最大匹配/2 。
// Asimple
#include <bits/stdc++.h>
#define INF 0xffffff
#define mod 1000000
#define swap(a, b, t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug( a ) cout << #a << " = " << a <<endl
#define abs(x) x<0?-x:x
#define srd(a) scanf("%d", &a)
#define src(a) scanf("%c", &a)
#define srs(a) scanf("%s", a)
#define srdd(a, b) scanf("%d %d",&a, &b)
#define srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
#define prd(a) printf("%d\n", a)
#define prdd(a, b) printf("%d %d\n",a, b)
using namespace std;
typedef long long ll;
const int maxn = 1505 ;
int n, m, num, T, k, x, y, len, ans;
int endx, endy, t;
bool vis[maxn];
int link[maxn];
vector< int > Map[maxn];
bool dfs( int x) {
int l ;
for ( int j= 0 ; j<Map[x].size(); j++ ) {
l = Map[x][j];
if ( ! vis[l] ) {
vis[l] = true ;
if ( link[l]==- 1 || dfs(link[l]) ) {
link[l] = x;
return true ;
}
}
}
return false ;
}
void solve() {
int res = 0 ;
CLS(link, - 1 );
for ( int i= 0 ; i<n; i++ ) {
CLS(vis, false );
if ( dfs(i) ) res ++ ;
}
prd(res / 2 );
}
void input() {
while ( ~ srd(n) ) {
for ( int i= 0 ; i<n; i++ ) Map[i].clear();
for ( int i= 0 ; i<n; i++ ) {
scanf( " %d: (%d) " , &x, & num);
for ( int j= 0 ; j<num; j++ ) {
srd(y);
Map[x].push_back(y);
Map[y].push_back(x);
// Map[x][y] = 1;
// Map[y][x] = 1;
}
}
solve();
}
}
int main(){
input();
return 0 ;
}
最后一道~ http://acm.hdu.edu.cn/showproblem.php?pid=1151
最小路径覆盖数，双向图，所以res/2。
// Asimple
#include <bits/stdc++.h>
#define INF 0xffffff
#define mod 1000000
#define swap(a, b, t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug( a ) cout << #a << " = " << a <<endl
#define abs(x) x<0?-x:x
#define srd(a) scanf("%d", &a)
#define src(a) scanf("%c", &a)
#define srs(a) scanf("%s", a)
#define srdd(a, b) scanf("%d %d",&a, &b)
#define srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
#define prd(a) printf("%d\n", a)
#define prdd(a, b) printf("%d %d\n",a, b)
using namespace std;
typedef long long ll;
const int maxn = 1005 ;
int n, m, num, T, k, x, y, len, ans;
int endx, endy, t;
int Map[maxn][maxn];
bool vis[maxn];
int link[maxn];
bool dfs( int x) {
for ( int j= 1 ; j<=n; j++ ) {
if ( Map[x][j] && ! vis[j] ) {
vis[j] = true ;
if ( link[j]==- 1 || dfs(link[j]) ) {
link[j] = x;
return true ;
}
}
}
return false ;
}
void solve() {
int res = 0 ;
CLS(link, - 1 );
for ( int i= 1 ; i<=n; i++ ) {
CLS(vis, false );
if ( dfs(i) ) res ++ ;
}
prd(n - res);
}
void input() {
srd(T);
while ( T -- ) {
srdd(n, num);
memset(Map, 0 , sizeof (Map));
for ( int i= 0 ; i<num; i++ ) {
srdd(x, y);
Map[x][y] = 1 ;
}
solve();
}
}
int main(){
input();
return 0 ;
}
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did238262