首页 > 其他 > 详细

洛谷2417 课程

时间:2018-10-17 13:50:05      阅读:163      评论:0      收藏:0      [点我收藏+]

原题链接

对于每一个课堂,向能够来这堂课的学生连边,然后跑二分图最大匹配,判断是否是完全匹配即可。
这里我是用的匈牙利算法。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int fi[N], di[N], ne[N], mtc[N], l;
bool v[N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline void add(int x, int y)
{
    di[++l] = y;
    ne[l] = fi[x];
    fi[x] = l;
}
bool dfs(int x)
{
    int i, y;
    for (i = fi[x]; i; i = ne[i])
        if (!v[y = di[i]])
        {
            v[y] = 1;
            if (!mtc[y] || dfs(mtc[y]))
            {
                mtc[y] = x;
                return true;
            }
        }
    return false;
}
int main()
{
    int i, j, x, n, m, t, s;
    t = re();
    while (t--)
    {
        n = re();
        re();
        memset(mtc, 0, sizeof(mtc));
        memset(fi, 0, sizeof(fi));
        l = 0;
        for (i = 1; i <= n; i++)
        {
            m = re();
            for (j = 1; j <= m; j++)
            {
                x = re();
                add(i, x + n);
            }
        }
        s = 0;
        for (i = 1; i <= n; i++)
        {
            memset(v, 0, sizeof(v));
            if (dfs(i))
                s++;
        }
        s ^ n ? printf("NO\n") : printf("YES\n");
    }
    return 0;
}

洛谷2417 课程

原文:https://www.cnblogs.com/Iowa-Battleship/p/9803375.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!