题目链接：

题目大意：一个老师带他的一群学生去旅游。带走的这群学生整体必须满足给出四个条件之一。问最多能带走多少学生。

解题思路：

二分图匹配题。最初我是这样考虑的：符合条件的学生连一条边，求最大匹配*2就行了。

但是问题却没那么简单。最大匹配保证的是多少人被匹配，至于匹配的东西是否有重复，它就不管了。如果简单的最大匹配数*2，那么中间有一些人被匹配了多次，也就是说人多了！

想要得到独立的人数，则必须使用最大独立集做法。

最大独立集的求法很简单：最大匹配的建图方式反过来！意思说完全不符合条件的才连边，在这题里，就是4个条件都不符合要求的学生连一条边。

然后求最大匹配数，ans=n-match/2。

注意这里为啥要除以2，因为你在建图的时候肯定图方便，用了两层for(1..n)判断i和j然后addedge了吧，这样就成了无向图了。

而Hungry是针对有向图的，所以match数成了原来的2倍，所以要除以2。

二分图中使用链式前向星也是挺好的。

 

#include "string"#include "cstdio"#include "cstring"#include "iostream"using namespace std;#define maxn 505int n,head[maxn],tol,link[maxn];bool vis[maxn];struct Edge{    int next,to;}e[maxn*maxn];struct person{    int h;    char sex;    string music,sport;}p[505];void addedge(int u,int v){    e[tol].to=v;    e[tol].next=head[u];    head[u]=tol++;}int abs(int x) {
   return x<0?-x:x;}bool judge(person a,person b){    if(abs(a.h-b.h)<=40&&a.sex!=b.sex&&a.music==b.music&&a.sport!=b.sport) return true;    else return false;}bool dfs(int u){    for(int i=head[u];i!=-1;i=e[i].next)    {        int v=e[i].to;        if(vis[v]) continue;        vis[v]=true;        if(!link[v]||dfs(link[v]))        {            link[v]=u;            return true;        }    }    return false;}int main(){    ios::sync_with_stdio(false);    int T;    cin>>T;    while(T--)    {        memset(link,0,sizeof(link));        memset(head,-1,sizeof(head));        tol=0;        cin>>n;        for(int i=1;i<=n;i++)        {            cin>>p[i].h>>p[i].sex>>p[i].music>>p[i].sport;        }        for(int i=1;i<=n;i++)          for(int j=1;j<=n;j++)            if(i!=j&&judge(p[i],p[j])) {addedge(i,j);}        int match=0;        for(int i=1;i<=n;i++)        {            memset(vis,false,sizeof(vis));            if(dfs(i)) match++;        }        printf("%d\n",n-match/2);    }}

 

2815370

Accepted

0 KB

233 ms

1464 B

2014-10-04 21:22:11