今天开始一天一道算法题的博客
今天的题是最大独立集，
对于最大独立集，本质上是求最大匹配，
对于这题，我们只要把不满足条件的人连起来，那么就构成了一张二分图，求好匹配以后，记得除以2，因为匈牙利算法在求匹配的时候，是从i=0到i=n-1的，这里是全部的点，所以相当于算了2次，
//烧死那对异性恋
#include<stdio.h>
#include<string.h>
#include<math.h>
#define maxn 505
struct edge
{
int to,next;
}mat[maxn];
int num,head[maxn*3],n;
char sex[maxn][1];
int high[maxn];
char stycle[maxn][101],sports[maxn][101];
bool vis[maxn];
int match[maxn];
void addedge(int from,int to)
{
mat[num].to=to;
mat[num].next=head[from];
head[from]=num++;
}
bool dfs(int u)
{
for (int i = head[u]; i !=-1; i=mat[i].next)
{
int v=mat[i].to;
if(!vis[v])
{
vis[v]=true;
if(match[v]==-1 || dfs(match[v]))
{
match[v]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int ans=0;
memset(match,-1,sizeof(match));
memset(head,-1,sizeof(head));
for(int i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
while(~scanf("%d",&n))
{
int i,j;
num=0;
for(i=0;i<n;i++)
scanf("%d%s%s%s",&high[i],sex[i],stycle[i],sports[i]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(sex[i][0]!=sex[j][0] && fabs(high[i]-high[j])<=40 && !strcmp(stycle[i],stycle[j]) && strcmp(sports[i],sports[j]))
addedge(i,j);
printf("%d\n",n-hungary()/2);
}
return 0;
}
如果有错，欢迎指出