TOJ3955: NKU ACM足球赛（并查集+map+细节题）-白红宇

TOJ3955: NKU ACM足球赛（并查集+map+细节题）

阅读量：5236 次

发布时间：2019-06-14

本文共 1425 字，大约阅读时间需要 4 分钟。

时间限制(普通/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

样例输出

思路：一看到“如果a和b认识，b和c认识，那么认为a和c也认识”这句话，马上想到并查集或者floyd算法。考虑到n非常大，直接拿并查集维护关系。

　　然后看到有几只队伍，那么就看每个小团队有多少人了，具体的可以拿stl里面的map。搞一下ma[fid(i)]++；代表这个小团队里面的人多一个。

之后就是细节了“每支队伍上限8人，下限5人；尽量满员”，这句话如果考虑清楚，就不会wa了，具体看代码。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #define LL long longusing 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
           
            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
            
             ::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\n",ans);}

转载于:https://www.cnblogs.com/Esquecer/p/8604470.html

你可能感兴趣的文章