PAT甲级-1114 Family Property (25 分)
发布日期:2022-02-10 08:11:02 浏览次数:6 分类:技术文章

本文共 1654 字,大约阅读时间需要 5 分钟。

题目:
分析:排序+并查集,主要就是数据的查找比较麻烦一点点
#include 
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         #include
         
          using namespace std;#define MAX 999999999int n,m;struct Node{ 
          
   int id,fa,mo;
int k;
vector child;
int estate,area;}node[10001];struct Node2{
   int id,num;
int as,aa;}node2[10001];int fa[10001];int visi[10001];int cmp(Node2 a,Node2 b){
   if(1.0*a.aa/a.num != 1.0*b.aa/b.num) return 1.0*a.aa/a.num > 1.0*b.aa/b.num;
return a.id < b.id;}int findFa(int x){
   if(x == fa[x]) return x;
return findFa(fa[x]);}void uni(int a,int b){
   fa[findFa(a)] = findFa(b);}int main(){
   cin>>n;
for(int i = 0;i < 10001;i++)
fa[i] = i;
for(int i = 0 ; i < n ; i++)
{
   int id,fa,mo,k;
cin>>id>>fa>>mo>>k;
node[id].fa = fa,node[id].mo = mo,node[id].id = id,node[id].k = k;
visi[id] = 1;
if(fa != -1){
   uni(fa,id);
visi[fa] = 1;
}
if(mo != -1){
   uni(mo,id);
visi[mo] = 1;
}
for(int j = 0 ; j < k ;j++)
{
   int c;cin>>c;
node[id].child.push_back(c);
uni(c,id);
visi[c] = 1;
}
int es,ar;
cin>>es>>ar;
node[id].estate = es,node[id].area = ar;
}
int cnt = 0;
for(int i = 0 ; i < 10001;i++)
if(fa[i] == i && visi[i] == 1)
cnt++;
cout< <
int cnt2 = 0;
for(int i = 0 ; i < 10001;i++)
{
   if(fa[i] == i && visi[i] == 1)
{
   int f = 0;
for(int j = 0 ; j < 10001 ; j ++)
{
   if(findFa(i) == findFa(j))
{
   if(f == 0){
   node2[cnt2].id = j;
f = 1;
}
node2[cnt2].num++;
node2[cnt2].as += node[j].estate;
node2[cnt2].aa += node[j].area;
}
}
cnt2++;
}
if(cnt2 == cnt)break;
}
sort(node2,node2+cnt,cmp);
for(int i = 0 ; i < cnt ; i++)
printf("%04d %d %.3f %.3f\n",node2[i].id,node2[i].num,1.0*node2[i].as / node2[i].num,1.0*node2[i].aa / node2[i].num);
return 0;}

转载地址:https://blog.csdn.net/qq_43567222/article/details/113883776 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:PAT甲级-1112 Stucked Keyboard (20 分)
下一篇:PAT甲级-1117 Eddington Number (25 分)

发表评论

最新留言

网站不错 人气很旺了 加油
[***.67.49.66]2022年08月15日 16时30分05秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章