（匹配）Courses -- hdu --1083

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1083

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82834#problem/C

一共有N个学生跟P门课程,一个学生可以任意选一

门或多门课,问是否达成:

1.每个学生选的都是不同的课(即不能有两个学生选同一门课)

2.每门课都有一个代表(即P门课都被成功选过)

现想组建一个委员会，委员会中的每个学生都要代表不同的课程，且每个课程都有它的代表。

算法分析：这正符合二分图最大匹配的条件。把课程作为二分图中X节点集合，得到最大匹配，如果匹配数等于课程数，则匹配与Y集合的交集，就可看成是这样一个委员会，则输出YES，否则，输出NO。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 305

#define INF 0x3f3f3f3f

int n, m, un, vn, G[N][N], used[N], p[N];

int Find(int u)

{

    for(int i=; i<=vn; i++)

    {

        if(G[u][i] && !used[i])

        {

            used[i] = ;

            if(p[i]==- || Find(p[i]))

            {

                p[i] = u;

                return ;

            }

        }

    }

    return ;

}

int hungary()  //匈牙利算法

{

    int ans = ;

    memset(p, -, sizeof(p));

    for(int i=; i<=un; i++)

    {

        memset(used, , sizeof(used));

        if(Find(i)) ans++;

    }

    return ans;

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        int i, j, v, k;

        scanf("%d%d", &n, &m);

        memset(G, , sizeof(G));

        for(i=; i<=n; i++)

        {

            scanf("%d", &k);

            for(j=; j<=k; j++)

            {

                scanf("%d", &v);

                G[i][v] = ;

            }

        }

        un = n;

        vn = m;

        if(un==hungary()) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

傻傻的刷题，加油！

巴特西

（匹配）Courses -- hdu --1083

最新文章

热门文章