题目地址:http://pat.zju.edu.cn/contests/pat-a-practise/1034

此题考查并查集的应用,要熟悉在合并的时候存储信息:

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <cstddef>
using namespace std; struct Person
{
int personalTime;
int gangTime;//记录以当前person为根的集合的gang 的总的通话时间
vector<string> members;//记录以当前person为根的集合的gang members
string root;
Person()
{
personalTime=;
gangTime=;
root="-1";
}
}; map<string,Person> tree;//并查集
map<string,int> gangs;//符合条件的gang string findRoot(string index)
{
if(tree[index].root=="-1") return index;
else
{
string tmp=findRoot(tree[index].root);
tree[index].root=tmp;
return tmp;
}
} string findHead(string root)//找出当前gang中具有最大weight的为gang head
{
vector<string> members=tree[root].members;
string gangHead=root;
int maxPersonalTime=tree[root].personalTime;
for(vector<string>::iterator iter=members.begin();iter!=members.end();++iter)
{
if(tree[*iter].personalTime>maxPersonalTime)
{
gangHead=*iter;
maxPersonalTime=tree[*iter].personalTime;
}
}
return gangHead;
} int _tmain(int argc, _TCHAR* argv[])
{
int N,K;
cin>>N>>K;
int i;
string Name1,Name2,root1,root2;
int Time;
for(i=;i<N;++i)
{
cin>>Name1>>Name2>>Time;
if(tree[Name1].members.size()==)
{
tree[Name1].members.push_back(Name1);
}
if(tree[Name2].members.size()==)
{
tree[Name2].members.push_back(Name2);
}
tree[Name1].personalTime+=Time;
tree[Name2].personalTime+=Time;
root1=findRoot(Name1);
root2=findRoot(Name2);
if(root1!=root2)
{
tree[root1].root=root2;
tree[root2].gangTime+=Time;
tree[root2].gangTime+=tree[root1].gangTime;
tree[root2].members.insert(tree[root2].members.end(),tree[root1].members.begin(),tree[root1].members.end());
}
else
{
tree[root2].gangTime+=Time;
}
}
for(map<string,Person>::iterator iter=tree.begin();iter!=tree.end();++iter)
{
if(iter->second.root=="-1"&&iter->second.members.size()>&&iter->second.gangTime>K)
{
string head=findHead(iter->first);
gangs[head]=iter->second.members.size();
}
}
size_t size=gangs.size();
cout<<size<<endl;
if(==size)
{
return ;
}
for(map<string,int>::iterator iter=gangs.begin();iter!=gangs.end();++iter)
{
cout<<iter->first<<" "<<iter->second<<endl;
}
return ;
}

最新文章

  1. mysql 报错max_allowed_packet处理办法
  2. Java基础之常用类
  3. AOP常用术语
  4. 【BZOJ】3456: 城市规划
  5. Android SDK镜像的介绍使用
  6. 注解:@Autowired
  7. Javascript编程模式(JavaScript Programming Patterns)Part 1.(初级篇)
  8. 启动genymotion后eclipse不能正常启动adb的处理办法
  9. 部署Cloudera Management for centos 7
  10. jQ的一些常识
  11. CentOS7安装最新版git教程
  12. TP5 model层 返回的对象转数组
  13. cmake中添加-fPIC编译选项方法
  14. window.location.href刷新页面
  15. OneAPM大讲堂 | Metrics, Tracing 和 Logging 的关系
  16. BZOJ1915[USACO 2010 Open Gold 1.Cow Hopscotch]——DP+斜率优化
  17. MyBatis基础入门《十五》ResultMap子元素(collection)
  18. python 比较两个yaml文件
  19. [Codeforces708E]Student&#39;s Camp
  20. EventHandler 与常见的.Net预定义委托

热门文章

  1. php分页类的二种调用方法(转载)
  2. 正确配置jstl的maven依赖,jar包冲突的问题终于解决啦
  3. DEPRECATED: Use of this script to execute hdfs command is deprecated.
  4. strstr函数与strcmp函数
  5. zepto源码学习-04 event
  6. 1319-n皇后问题
  7. 了解实时媒体的播放(RTP/RTCP 和 RTSP)
  8. ARM的NEON协处理器是什么
  9. Android 滑动菜单SlidingMenu
  10. javascript模板引擎Mustache