时间限制(普通/Java):5000MS/15000MS 内存限制:65536KByte
描述
NKU ACM最近要举行足球赛，作为此次赛事的负责人，Lee要对报名人员进行分队。分队要遵循如下原则：
一个人不能加入多支队伍；
不认识的人不能分在同一队；
如果a和b认识，b和c认识，那么认为a和c也认识；
每支队伍上限8人，下限5人；
尽量使队伍满员。
由于参赛人数很多，Lee表示无能为力，所以请你帮助Lee编程解决比赛有多少队伍。
输入
第一行输入两个整数，n和m，n(1<=n<=300000)代表报名人数,m(1<=m<=500000)代表关系数。接下来m行每行两个整数a(1<=a<=n)和b(1<=b<=n)表示a和b认识。
输出
输出一行，包含一个整数，表示队伍数量。
样例输入
11 10
1 2
2 3
2 6
3 4
4 5
5 6
7 9
9 11
11 8
8 10
样例输出
2
思路：一看到“如果a和b认识，b和c认识，那么认为a和c也认识”这句话，马上想到并查集或者floyd算法。考虑到n非常大，直接拿并查集维护关系。
然后看到有几只队伍，那么就看每个小团队有多少人了，具体的可以拿stl里面的map。搞一下ma[fid(i)]++； 代表这个小团队里面的人多一个。
之后就是细节了“每支队伍上限8人，下限5人；尽量满员”，这句话如果考虑清楚，就不会wa了，具体看代码。
#include<iostream> #include<algorithm> #include<cstdio> #include<stack> #include<vector> #include<map> #define LL long long using namespace std; int pre[310000],n; int fid(int x){return pre[x] == x ? x : pre[x] = fid(pre[x]) ;} void join(int x,int y){fid(x)!=fid(y)?pre[fid(x)]=fid(y):0;} void init(){for(int i = 0 ;i <= n ; i++)pre[i] = i;} map<int,int>ma; int main() { int m; scanf("%d %d",&n,&m); init(); while(m--){ int x,y; scanf("%d %d",&x,&y); join(x,y); } int ans = 0; for(int i = 1 ; i <= n ; i++) ma[fid(i)]++;//每个小团体的人数存在map中 map<int,int>::iterator it = ma.begin(); for(;it != ma.end();it++){ int t = it->second; for(int i = 8 ; i >= 5 ; i--){ if(t >= i){ ans += t/i; t %= i; } }//尽量满员 } printf("%d ",ans); }