算法 并查集
思路:刚看题目有点像是图论一样hhh
首先先存数据,以用ID来存数据,这里可以直接哈希,因为ID范围0-1W,然后标记改ID(为了确定家中最小的ID)并用ID来维护各项数据(房产数量和房产面积)
然后使用并查集来维护最小ID并将家产累加到最小ID中
st数组一开始是用来标记资产归属哪个ID,然后将资产归到最小ID中
C++ 代码
#include<bits/stdc++.h>
#define pb push_back
#define pp poop_back
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=10010,mod=1e9+7;
struct node{
int id,to;
}node[N];
int m=0;
int f[N];
int c[N],fc[N],ft[N];
bool st[N];
int find(int x)
{
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
struct family{
int id,a;
double aft,afc;
bool operator < (const family &t) const{
if(t.afc!=afc) return t.afc<afc;
else return t.id>id;
}
};
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int id,fa,ma,k;cin>>id>>fa>>ma>>k;
st[id]=1;
if(fa!=-1) node[m++]={id,fa};
if(ma!=-1) node[m++]={id,ma};
for(int j=1;j<=k;j++)
{
int t;cin>>t;
node[m++]={id,t};
}
cin>>ft[id]>>fc[id];
}
for(int i=0;i<=10000;i++) f[i]=i,c[i]=1;
for(int i=0;i<m;i++)
{
int a=node[i].id,b=node[i].to;
int fa=find(a),fb=find(b);
//cout<<fa<<" "<<fb<<endl;
if(fa!=fb)
{
if(fa>fb)
{
st[fa]=0;
st[fb]=1;
swap(fa,fb);
}
f[fb]=fa;
c[fa]+=c[fb];
fc[fa]+=fc[fb];
ft[fa]+=ft[fb];
}
}
vector<family>q;
for(int i=0;i<=10000;i++)
{
if(st[i]&&f[i]==i)
{
q.pb({i,c[i],(double)ft[i]/c[i],(double)fc[i]/c[i]});
}
}
sort(q.begin(),q.end());
cout<<q.size()<<endl;
for(int i=0;i<q.size();i++)
{
printf("%04d %d %.3lf %.3lf\n",q[i].id,q[i].a,q[i].aft,q[i].afc);
}
return 0;
}