pku 1469 courses

首先建立二分圖,把P門課程作爲X集合,N個人作爲Y集合,對二分圖進行完備匹配判定。方法是用匈牙利算法求出最大匹配,判斷最大匹配數是否爲P即可。

/* 
 * Problem: pku1469 courses
 * Author: Guo Jiabao
 * Time: 2009.3.25 21:45
 * State: Solved
 * Memo: 求完備匹配
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXP=101,MAXN=301;
using namespace std;
struct edge
{
    edge *next;
    int t;
};
edge *V[MAXP];
edge ES[MAXN*MAXP];
int N,P,EC,Match[MAXN],mat;
bool vis[MAXN];
inline void addedge(int a,int b)
{
    ES[++EC].next=V[a];
    (V[a]=&ES[EC])->t=b;
}
void init()
{
    int i,j,C,a;
    scanf("%d%d",&P,&N);
    EC=-1;
    for (i=1;i<=P;i++)
    {
        scanf("%d",&C);
        V[i]=0;
        for (j=1;j<=C;j++)
        {
            scanf("%d",&a);
            addedge(i,a);
        }
    }
    memset(Match,0,sizeof(Match));
    mat=0;
}
bool path(int i)
{
    for (edge *k=V[i];k;k=k->next)
    {
        int j=k->t;
        if (!vis[j])
        {
            vis[j]=true;
            if (Match[j]==0 || path(Match[j]))
            {
                Match[j]=i;
                return true;
            }
        }
    }
    return false;
}
void hungary()
{
    for (int i=1;i<=P;i++)
    {
        memset(vis,0,sizeof(vis));
        if (path(i))
            mat++;
    }
    if (mat==P)
        printf("YESn");
    else
        printf("NOn");
}
int main()
{
    int i,T;
    freopen("courses.in","r",stdin);
    freopen("courses.out","w",stdout);
    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        init();
        hungary();
    }
    return 0;
}

相關日誌