题目大意：一个老师带他的一群学生去旅游。带走的这群学生整体必须满足给出四个条件之一。问最多能带走多少学生。
解题思路：
二分图匹配题。最初我是这样考虑的：符合条件的学生连一条边，求最大匹配*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 505
int 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[];
void addedge(int u,int v)
{
e[tol].to=v;
e[tol].next=head[u];
head[u]=tol++;
}
int abs(int x) {return x<?-x:x;}
bool judge(person a,person b)
{
if(abs(a.h-b.h)<=&&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!=-;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,,sizeof(link));
memset(head,-,sizeof(head));
tol=;
cin>>n;
for(int i=;i<=n;i++)
{
cin>>p[i].h>>p[i].sex>>p[i].music>>p[i].sport;
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(i!=j&&judge(p[i],p[j])) {addedge(i,j);}
int match=;
for(int i=;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(dfs(i)) match++;
}
printf("%d\n",n-match/);
}
}
| 2815370 | neopenx | UVALive 3415 | Accepted | 0 KB | 233 ms | C++ 4.5.3 | 1464 B | 2014-10-04 21:22:11 |