UVALive-3415 Guardian of Decency （最大独立集）

题目大意：一个老师要带一些学生去春游，但是要带的学生中任意两个人都满足下面四个条件中的至少一个：1、性别相同；2、身高差大与40公分；3、最喜欢的音乐类型不同；4、最喜欢的体育运动相同。问老师最多能带多少个学生？

题目分析：最大独立集问题。最大独立集+最小覆盖集=全集。将学生视为节点，对于任意两个不满足上述四个条件中的学生，连一条有向边。这就意味着一条边的两个端点至少有一个不能去春游，这与一条边中至少有一个去春游恰好互补，后者正是最小覆盖问题。

代码如下：

# include<iostream>

# include<cstdio>

# include<string>

# include<vector>

# include<cstring>

# include<algorithm>

using namespace std;

# define REP(i,s,n) for(int i=s;i<n;++i)

# define CL(a,b) memset(a,b,sizeof(a))

# define CLL(a,b,n) fill(a,a+n,b)

const int N=505;

struct student

{

    int high;

    char sex;

    string music,PE;

};

student stu[N];

int n,vis[N],link[N];

vector<int>G[N];

bool ok(int i,int j)

{

    if(stu[i].sex==stu[j].sex) return false;

    if(stu[i].PE==stu[j].PE) return false;

    if(abs(stu[i].high-stu[j].high)>40) return false;

    if(stu[i].music!=stu[j].music) return false;

    return true;

}

bool dfs(int x)

{

    REP(i,0,G[x].size()){

        int y=G[x][i];

        if(vis[y]) continue;

        vis[y]=1;

        if(link[y]==-1||dfs(link[y])){

            link[y]=x;

            return true;

        }

    }

    return false;

}

int match()

{

    int res=0;

    CL(link,-1);

    REP(i,1,n+1){

        CL(vis,0);

        if(dfs(i)) ++res;

    }

    return res;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        REP(i,1,n+1) G[i].clear();

        REP(i,1,n+1) cin>>stu[i].high>>stu[i].sex>>stu[i].music>>stu[i].PE;

        REP(i,1,n+1){

            REP(j,i+1,n+1) if(ok(i,j)){

                G[i].push_back(j);

                G[j].push_back(i);

            }

        }

        int ans=match();

        printf("%d\n",n-ans/2);

    }

    return 0;

}