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