PAT 甲级 1114
这道题网上大多的解法都是使用并查集，我觉得也可以考虑使用图的遍历来做，将每个家庭都看做是一个连通的图，那我们需要做的就是遍历每个连通图，并统计他们的每个连通图的area和estate即可，使用vector容器来存储所有人的id，再从小到大进行排序，也可以保证每个家庭的id是该家庭中最小的id。代码如下：
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct people{
int estate,area;
people()
{
estate=0;
area=0;
}
}p[10010];
struct family{
int id,num;
double sets,area;
}f[1010];
vector<int> Adj[10010],human;
bool vis[10010]={false};
int familynum=0;
bool cmp(family a,family b)
{
if(a.area!=b.area) return a.area>b.area;
else return a.id<b.id;
}
void deal(int parent,int child)
{
if(!vis[child])
{
vis[child]=true;
human.push_back(child);
}
if(parent==-1) return;
Adj[parent].push_back(child);
Adj[child].push_back(parent);
if(!vis[parent])
{
vis[parent]=true;
human.push_back(parent);
}
}
void BFS(int root)
{
queue<int> q;
q.push(root);
vis[root]=true;
while(!q.empty())
{
int k=q.front();
q.pop();
f[familynum].num++;
f[familynum].sets+=p[k].estate;
f[familynum].area+=p[k].area;
for(int i=0;i<Adj[k].size();i++)
if(!vis[Adj[k][i]])
{
q.push(Adj[k][i]);
vis[Adj[k][i]]=true;
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int a,b,c,d,e;
scanf("%d %d %d %d",&a,&b,&c,&d);
deal(b,a);
deal(c,a);
for(int j=0;j<d;j++)
{
scanf("%d",&e);
deal(a,e);
}
scanf("%d %d",&p[a].estate,&p[a].area);
}
sort(human.begin(),human.end());
memset(vis,false,sizeof(vis));
for(int i=0;i<human.size();i++)
{
if(!vis[human[i]])
{
f[familynum].id=human[i];
BFS(human[i]);
f[familynum].sets=(double)(f[familynum].sets*1.0/f[familynum].num);
f[familynum].area=(double)(f[familynum].area*1.0/f[familynum].num);
familynum++;
}
}
sort(f,f+familynum,cmp);
printf("%d\n",familynum);
for(int i=0;i<familynum;i++)
{
printf("%04d %d %.3f %.3f\n",f[i].id,f[i].num,f[i].sets,f[i].area);
}
return 0;
}