二分图匹配[匈牙利算法]

啊哈磊

一个不错的讲义 jiangyi.doc (33 KB, 下载次数: 188)

2013-2-20 20:38 上传

点击文件名下载附件

n,m,t。n个牛，m个牛棚，t个关系，最多有多少个不同的匹配。

【输入数据】
5 5 11
1 2
1 5
2 2
2 3
2 5
3 1
3 5
4 1
4 2
4 5
5 5

【输出数据】
4[code=Cpp width=740px]#include <stdio.h>

#include <string.h>

#define MAXN 201

int graph[MAXN][MAXN];
int ymatch[MAXN];                        /* Y对应在X中匹配的点 */
int visited[MAXN];

int dfs(int p, int m)
{
        int i;
        for (i=1; i<=m; i++)
        {
                if (graph[p] == 1 && visited == -1)
                {
                        visited = 1;                                /* 标记i为已查找过 */
                        if (ymatch == -1                        /* 如果i未在前一个匹配M中 */
                                || dfs(ymatch, m))        /* 在匹配M中，但是从与i相邻的节点出发可以有增广路 */
                        {
                                ymatch = p;                        /* 记录查找成功记录（增广路取反） */
                                return 1;                                /* 返回查找成功 */
                        }
                }
        }
        return 0;
}

int matches(int n, int m)
{
        int i,j, sum = 0;
        for(i=1;i<MAXN;i++)
           ymatch=-1;

        for (i=1; i<=n; i++)                                                        /* 遍历X集合的每一个点 */
        {
                for(j=1;j<MAXN;j++)                     /* 清空上次搜索时的标记 */
               visited[j]=-1;
                if (dfs(i, m))                                                        /* 找到交错链，匹配数加1 */
                        sum++;
        }

        return sum;

}

int main()
{
        int m, n, e, i, j, t1, t2;
        freopen("hungary.in", "r", stdin);
        freopen("hungary.out", "w", stdout);


        while (scanf("%d%d%d", &n, &m, &e) != EOF)
        {
                for (i=1; i<=e; i++)
                {
                        scanf("%d%d", &t1, &t2);
                        graph[t1][t2] = 1;
                }

                printf("%d\n", matches(n, m));
        }

        return 0;
}[/code]

4399APPLE

先来挖一下
再来补充一句....

我大 Dinic 大法好

逸飞扬_VbCNT

看不懂啊