题意
有 N 个人，每个人有四个属性：
W，Sex，Mu，Sp
两个人 u 和v 不能出现在同一个集合当且仅当满足：
|Wu−Wv|≤40，Sexu≠Sexv
Muu=Muv，Spu≠Spv
问最多可以选出多少人使得这些人在同一个集合
N≤500 ，最多100组数据
解法
二分图最大匹配：
这道题有两种思考方向：
①.不排斥的人之间连边，那么问题转化为求最大团，很麻烦，不作考虑
②.排斥的人之间连边，那么问题转化为求最大独立集，比较简单，所以我们采取此种方法
最大独立集一般只有树的最大独立集和二分图的最大独立集两种，本题显然不可能是树，于是考虑怎么构建二分图
很明显，因为 Sex 属性只有两种（不是男，就是女），所以可以按照 Sex 将图分为两个部分，然后再根据另外三个条件进行连边（本题的 N 比较小，所以使用矩阵方便一些）
然后就是要求最大独立集了，这里有一个结论：二分图的最大独立集=总点数-最小覆盖数，二分图的最小覆盖数=最大匹配
（证明请看博客：）
所以使用匈牙利算法求出最大匹配即可
复杂度
O（
T∗N∗|E| ）
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<map>
#define Rint register int
#define Lint long long int
using namespace std;
const int INF=0x3f3f3f3f;
const int E=100010;
const int N=510;
bool g[N][N],vis[N],sex[N];
int match[N],w[N];
int mu[N],cntm;
int sp[N],cnts;
int T,n,cnt;
map<string,int> f,v;
int abs(Rint x)
{return x<0 ? -x : x ;
}
bool find(Rint k)
{for(Rint i=1;i<=n;i++)if( !vis[i] && g[k][i] ){vis[i]=1;if( !match[i] || find( match[i] ) ){match[i]=k;return true ;}}return false ;
}
int main()
{char cs,a[N],b[N];scanf("%d",&T);while( T-- ){cnt=cntm=cnts=0;f.clear(),v.clear();scanf("%d",&n);for(Rint i=1;i<=n;i++){scanf("%d %c%s%s",&w[i],&cs,a,b);if( !f[a] ) f[a]=++cntm;if( !v[b] ) v[b]=++cnts;mu[i]=f[a],sp[i]=v[b];sex[i]=(cs=='M');match[i]=0;}for(Rint i=1;i<=n;i++)for(Rint j=i+1;j<=n;j++)if( sex[i]==sex[j] || abs( w[i]-w[j] )>40 || mu[i]!=mu[j] || sp[i]==sp[j] ) g[i][j]=g[j][i]=0;else g[i][j]=g[j][i]=1;for(Rint i=1;i<=n;i++){for(Rint j=1;j<=n;j++) vis[j]=0;if( find( i ) ) cnt++;}printf("%dn",n-cnt/2);}return 0;
}本文发布于:2024-01-31 11:57:59，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170667348028356.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
