[HihoCoder]#1122 : 二分图二•二分图最大匹配之匈牙利算法

华电北风吹
天津大学认知计算与应用重点实验室
2016-07-02

题目链接：
http://hihocoder.com/problemset/problem/1122?sid=812977

题目分析：
link数组用来保存匹配边，每次dfs找到增广路径的时候(返回1)，更新匹配边(双向连接)。然后对所有的节点查看一遍是否存在增广路径即可。除此之外，也可以用邻接表来避免遍历寻找边。

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

#define MAXLENGTH 1001

using namespace std;
int N, M;
int map[MAXLENGTH][MAXLENGTH];
int link[MAXLENGTH];
bool visited[MAXLENGTH];

int dfs(int dd)
{
for (int i = 1; i <= N; i++)
    {
if (visited[i] == false && map[dd][i] == 1)
        {
            visited[i] = true;
if (link[i] == -1 || dfs(link[i]))
            {
                link[i] = dd;
                link[dd] = i;
return 1;
            }
        }
    }
return 0;
}

int main()
{
scanf("%d %d", &N, &M);
int i, j;
int u, v;
memset(map, 0, sizeof(map));
memset(link, -1, sizeof(link));

for (i = 0; i<M; i++)
    {
scanf("%d %d", &u, &v);
map[u][v] = 1;
map[v][u] = 1;
    }
int count = 0;
for (i = 1; i <= N; i++)
    {
if (link[i] == -1)
        {
memset(visited, false, sizeof(visited));
            count += dfs(i);
        }       
    }
printf("%d\n", count);
return 0;
}