POJ1426 最小獨立點集

romantically involved .... 有人吐槽男男之間也能有好感...無視！！這題就是男的對女的才有...也就是圖就是個二分圖...)...有好感的男女不能分在一起....問最後能分在一起的人數最多是多少..

   這道題一看就想到二分圖...但我就是因為對最小獨立點集的性質以及與最小點覆寫的關系不清楚...導緻卡了蠻久...後來去找了資料才明白...最小獨立點集 = 頂點數 - 最小點覆寫數...又最小點覆寫 = 最大比對數...so...

最小獨立點集 = 頂點數 - 最大比對數

#include<iostream>
#define MAXN 510
using namespace std;
int n,match[MAXN];
bool map[MAXN][MAXN],used[MAXN];
int input()
{
    int data=0;
    char c; 
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9')
    {
        data=data*10+c-'0';
        c=getchar();      
    }
    return data;
}
bool ok(int num)
{
    int i;
    for (i=0;i<n;i++)
    if (!used[i] && map[num][i])
    {
         used[i]=true;           
         if (match[i]==-1 || ok(match[i]) )
         {
             match[i]=num;
             return true;                 
         }          
    }    
    return false;
}
int main()
{ 
    while (~scanf("%d",&n))
    {
        int i,h,p,k;
        memset(map,false,sizeof(map));
        for (i=0;i<n;i++)
        {
            h=input();
            k=input();
            while (k--)
            {
                p=input();
                map[h][p]=true;  
            }
        }    
        memset(match,-1,sizeof(match));
        k=0;
        for (i=0;i<n;i++)
        {
            memset(used,false,sizeof(used)); 
            if (ok(i)) k++;
        } 
        printf("%d\n",(2*n-k)/2);
    }
    return 0;   
}