首页 > 代码库 > poj 1466 Girls and Boys (最大独立集)

poj 1466 Girls and Boys (最大独立集)

链接:poj 1466

题意:有n个学生,每个学生都和一些人有关系,现在要你找出最大的人数,使得这些人之间没关系

思路:求最大独立集,最大独立集=点数-最大匹配数
分析:建图时应该是一边是男生的点,一边是女生的点连边,但是题目中没说性别的问题,只能将每个点拆成两个点,一个当作是男的点,一个当作是女的点了,然后连边.由于关系是相互的,这样就造成了边的重复。也就是边集是刚才的二倍,从而导致了最大匹配变成了原本的二倍,因此,此时最大独立集=点数-最大匹配数/2.

#include<stdio.h>
#include<string.h>
int n,edge[510][510],link[510],used[510];
int dfs(int pos)
{
    int i;
    for(i=0;i<n;i++){
        if(edge[pos][i]&&!used[i]){
            used[i]=1;
            if(link[i]==-1||dfs(link[i])){
                link[i]=pos;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int i,j,a,b,s,m;
    while(scanf("%d",&n)!=EOF){
        memset(edge,0,sizeof(edge));
        for(i=0;i<n;i++){
            scanf("%d: (%d)",&a,&m);
            for(j=0;j<m;j++){
                scanf("%d",&b);
                edge[a][b]=1;  //建图
            }
        }
        memset(link,-1,sizeof(link));
        s=0;
        for(i=0;i<n;i++){
            memset(used,0,sizeof(used));
            s+=dfs(i);
        }
        printf("%d\n",n-s/2);  //记住要减去最大匹配数的一半
    }
    return 0;
}



poj 1466 Girls and Boys (最大独立集)