今天做个题目，学长说用匈牙利算法（求最大匹配），但是程序模板不知道，求高人，帮写下面程序，
题目：电视台做了关于猫狗喜好投票，喜欢猫的观众不喜欢狗，问，电视台最多能满足都少观众需求。

Sample Input
2/*表示几组测试数据*/
1 1 2/*第一个数表示猫的数量，第二个数表示狗的数量，第三个数表示投票观众的数量*
C1 D1/*这是第一个人投票结果，第一票投喜欢票，第二票投反对票，所以C1表示他喜欢第一只猫，D1表示讨厌第一只狗，以下类推*/
D1 C1
1 2 4
C1 D1
C1 D1
C1 D2
D2 C1
 
Sample Output
1/*表示最多能满足多少观众（投票者），即投票人数减去匈牙利算法最大匹配数/
3

看不懂，能举个比较易懂的例子么

看了半天的匈牙利算法球二分图的最大匹配，没看懂。
关注一下吧。
我也想知道怎么算。。。

#include<stdio.h>
#include<string.h>
 
int map[1000][1000];
int con[1000];
int vis[1000];
int max = 0;
int n, m;
 
int find(int p)
{
    int i;
    for(i=1; i<=n; i++)
    {
        if(map[p][i] && !vis[i])
        {
            vis[i] = 1;
            if(!con[i] || find(con[i]))
            {
                con[i] = p;
                return 1;
            }
        }
    }
    return 0;
}
 
int main(void)
{
    int i;
    int x, y;
     
    memset(map, 0, sizeof(map));
    memset(con, 0, sizeof(con));
     
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d", &x, &y);
        map[x][y] = 1;
    }
    for(i=1; i<=n; i++)
    {
        memset(vis, 0, sizeof(vis));
        max += find(i);
    }
    printf("%d\n", max);
    for(i=1; i<=n; i++)
    {
        if(con[i])
        {
            printf("%d %d\n", con[i], i);
        }
    }
     
    return 0;
}

我给你的不是原题的代码，是基本的匈牙利代码。

输出的是匹配边。


你的问题的答案就是求的匹配的补集

回复 5楼 rofor

恩，谢谢你了，你还能描述一下你的那个问题么？