匈牙利算法详解

当然，匹配开始时我们任意选择一边的所有点为起始点找增广路径，由增广路的性质可以看出，每找到一条增广路径，匹配

数增加1。

很多问题都可以转化为二分图匹配模型。二分图有如下几种常见变形：

(1)二分图的最小顶点覆盖 

最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。

Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。

(2)DAG图的最小路径覆盖 

用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。

结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）

(3)二分图的最大独立集

最大独立集问题： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值

结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1054

题意：给定一棵树，求最小顶点覆盖。由于本题是双向图，所以最小顶点覆盖等于双向图的最大匹配/2。本题属于模板题。

这种模型一般适用二分图两边的点都一样，否则一般都是建立有向图来匹配的。

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 2005;

bool vis[N];
int link[N],head[N];
int cnt,n;

struct Edge
{
    int to;
    int next;
};

Edge edge[N*N];

void Init()
{
    cnt = 0;
    memset(head,-1,sizeof(head));
}

void add(int u,int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

bool dfs(int u)
{
    for(int i=head[u];~i;i=edge[i].next)
    {
        int v = edge[i].to;
        if(!vis[v])
        {
            vis[v] = 1;
            if(link[v] == -1 || dfs(link[v]))
            {
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

int match()
{
    int ans = 0;
    memset(link,-1,sizeof(link));
    for(int i=0;i<n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i)) ans++;
    }
    return ans;
}

int main()
{
    while(~scanf("%d",&n))
    {
        Init();
        for(int i=0;i<n;i++)
        {
            int u,v,k;
            scanf("%d:(%d)",&u,&k);
            while(k--)
            {
                scanf("%d",&v);
                add(u,v);
                add(v,u);
            }
        }
        printf("%d\n",match()>>1);
    }
    return 0;
}

分析：本题是比较裸的二分图匹配题，直接套模板即可。

题目：http://poj.org/problem?id=1469

分析：同样是模板题。

题目：http://poj.org/problem?id=3041

题意：假如你现在处于一个N*N的矩阵中，这个矩阵里面有K个障碍物，你拥有一把武器，一发弹药一次能消灭一行或者一列的障碍物，求消灭全部的障碍物需要最少的弹药数。

分析：本问题是二分图的一个很经典的模型，我们可以这样考虑：我们以所有的行为二分图的左顶点，所有的列为二分图的右顶点，那么如果位于坐标P(x,y)有障碍物，我们就连一条边，然后我们只需要最少的顶点覆盖所有的边即可。这样就是二分图的最小顶点覆盖问题了，我们又知道最小顶点覆盖等于二分图最大匹配。

题目：http://poj.org/problem?id=2226

题意：给出一个N*M的图，其中图中每一个格子要么是'*'，要么是'.'，'*'代表稀泥，'.'代表草地，现在要用一些木板把所有的稀泥盖住，但是不能盖住草地。一张木板只能盖住一行或者一列中的一部分，求至少要用多少木板把所有的稀泥盖住。

分析：本题与上题不同的是，木板不能盖住整行或者整列，但是我们可以把所有的横向连续的稀泥格子和所有竖向连续的稀泥格子编上号，然后如果有交叉的就连一条边，这就是建图部分。然后进一步转化为最小顶点覆盖问题。

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 55;
const int M = 555;

char map[N][N];
int col[N][N],row[N][N];
int link[M],head[M];
bool vis[M];
int cnt,n,m;
int R,C;

struct Edge
{
    int to;
    int next;
};

Edge edge[M*M];

void Init()
{
    cnt = 0;
    memset(head,-1,sizeof(head));
    memset(col,0,sizeof(col));
    memset(row,0,sizeof(row));
}

void add(int u,int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

bool dfs(int u)
{
    for(int i=head[u]; ~i; i=edge[i].next)
    {
        int v = edge[i].to;
        if(!vis[v])
        {
            vis[v] = 1;
            if(link[v] == -1 || dfs(link[v]))
            {
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

int match()
{
    int ans = 0;
    memset(link,-1,sizeof(link));
    for(int i=1; i<=R; i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i)) ans++;
    }
    return ans;
}

int main()
{
    while(cin>>n>>m)
    {
        Init();
        R = C = 0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>map[i][j];
                if(map[i][j] == '*')
                {
                    if(row[i][j-1]) row[i][j] = row[i][j-1];
                    else row[i][j] = ++R;
                    if(col[i-1][j]) col[i][j] = col[i-1][j];
                    else col[i][j] = ++C;
                }
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(map[i][j] == '*')
                    add(row[i][j],col[i][j]);
        printf("%d\n",match());
    }
    return 0;
}