1 条题解

  • 0
    @ 2025-10-8 16:49:24
    #include<bits/stdc++.h>
    using namespace std;
    int match[110], chw[110], tsp;
    vector<int> G[310];
    bool findmuniu(int x)
    {
        for(int y : G[x])
        {
            if(chw[y] != tsp)
            {
                chw[y] = tsp;
                if((match[y] == 0) || (findmuniu(match[y]) == 1))
                {
                    match[y] = x;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main()
    {
        int n1, n2; scanf("%d", &n1); n2 = 7*12; // 构图:公牛是课程,母牛是上课时间(某天的某节课)
        for(int i = 1; i <= n1; i++)
        {
            int t; scanf("%d", &t);
            while(t--)
            {
                int p, q; scanf("%d%d", &p, &q);
                int y = (p-1)*12 + q;
                G[i].emplace_back(y);
            }
        }
        int ans = 0;
        memset(match, 0, sizeof(match));
        memset(chw, 0, sizeof(chw));
        for(int i = 1; i <= n1; i++)
        {
            tsp = i;
            if(findmuniu(i) == 1) ans++;
        }
        printf("%d", ans);
        return 0;
    }
    
    • 1

    *【二分图:最大匹配】上课[POJ2239]

    信息

    ID
    316
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    183
    已通过
    72
    上传者