poj 1469 courses(二分匹配)

解题思路

题意：
    有N个学生和P个courses（这个单词不知道该怎么翻才合适），每个学生可以去访问0个或多个courses，我们的任务是判断能不能组成一个正好有p个学生的委员会符合以下两个条件。（1）每个学生代表一个不同的courses （2）每个courses有一个学生代表。

 

思路：

   将题意简单化就是有两组点A（course）和B（student），从A中每个点出发有count(i)条路径连接到B中的不同的点，求出A跟B的最大匹配，看是否能使A中每个点都成为饱和点。

   看这个二分图的最大匹配数是否等于A中的点数。

源程序

 

 

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define P 105
#define N 305

int g[P][N], used[N], mat[N];
int match;

int find(int k)
{
    int i, j;
    for(i=1; i<=g[k][0]; i++)
    {
        j = g[k][i];
        if(!used[j])
        {
            used[j] = 1;
            if(!mat[j] || find(mat[j]))
            {
                mat[j] = k;
                return 1;
            }
        }
    }
    return 0;
}

void hungary(int p)
{
    int i;
    for(i=1; i<=p; i++)
    {
        match += find(i);
        memset(used, 0, sizeof(used));
    }
}

int main()
{
    int i, j;
    int n, p, t;

    freopen("in.txt", "r", stdin);
    
    scanf("%d", &t);
    while(t--)
    {
        memset(g, 0, sizeof(g));
        memset(mat, 0, sizeof(mat));
        scanf("%d%d", &p, &n);
        
        for(i=1; i<=p; i++)
        {
            scanf("%d", &g[i][0]);
            for(j=1; j<=g[i][0]; j++)
            {
                scanf("%d", &g[i][j]);
            }
        }
        match = 0;
        hungary(p);
        if(match == p)
            printf("YES\n");
        else printf("NO\n");
    }
    getch();
    return 0;
}

Memory: 284K

Time: 391MS