一个不错的讲义
jiangyi.doc
(33 KB, 下载次数: 188)
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]
|