1114 Family Property（25分）

本文主要是介绍1114 Family Property（25分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目翻译：

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：家庭成员的最小编号家庭人口数人均房产套数人均房产面积。其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。

题解思路：

并查集或者dfs

代码：

dfs代码：

#include<bits/stdc++.h>
using namespace std;
int N;
struct node {int set = 0, area = 0;
};
node value[10000];//存储结点的值
vector<int> v[10000];//用于表示邻居关系
int visited[10000],rea[10000];//是否访问过，是否是关系网中的结点
struct results {//存储结果int min_id, num, sum1, sum2;
};
vector<results> R;int min_id = 0 , num = 0, S1 = 0, S2 = 0;//用于得到dfs的结果void dfs(int curnode)
{visited[curnode] = 1;if (curnode < min_id)min_id = curnode;for (auto i : v[curnode]){if (visited[i] == 0){dfs(i);num++, S1 += value[i].set, S2 += value[i].area;}}
}bool comp(results r1, results r2)
{if (r1.sum2 / double(r1.num) > r2.sum2 / double(r2.num))return true;else if (r1.sum2 / double(r1.num) == r2.sum2 / double(r2.num))return r1.min_id < r2.min_id;elsereturn false;
}int main()
{cin >> N;int id1, id2, id3, k;for (int i = 0;i < N;i++){cin >> id1 >> id2 >> id3;rea[id1] = 1;node n;if (id2 != -1){rea[id2] = 1;v[id1].push_back(id2);v[id2].push_back(id1);}if (id3 != -1){rea[id3] = 1;v[id1].push_back(id3);v[id3].push_back(id1);}cin >> k;while (k--){int child;cin >> child;v[id1].push_back(child);v[child].push_back(id1);}cin >> value[id1].set >> value[id1].area;}for (int i = 0;i < 10000;i++){if (!visited[i] && rea[i]){min_id = i, num = 1, S1 = value[i].set, S2 = value[i].area;//赋初值dfs(i);results temp;temp.min_id = min_id, temp.num = num, temp.sum1 = S1, temp.sum2 = S2;R.push_back(temp);}}sort(R.begin(), R.end(), comp);cout << R.size() << endl;for (auto i : R)cout <<setw(4)<<setfill('0')<<i.min_id << " " << i.num << " " << fixed << setprecision(3) << i.sum1 / double(i.num) << " " << fixed << setprecision(3) << i.sum2 / double(i.num) << endl;
}

并查集实现;

#include<bits/stdc++.h>
using namespace std;
int N;
struct node {int set = 0, area = 0;
};
node value[10000];
vector<int> v[10000];//邻居关系
int f[10000];//并查集存储结点的父亲节点
vector<int> cv;//输入的最左侧的值
int rea[10000];//区分是否为原始点
struct results {int min_id = 10000, num = 0, sum1 = 0, sum2 = 0, tag = 0;
};
vector<results> R;bool comp(results r1, results r2)
{if (r1.sum2 / double(r1.num) > r2.sum2 / double(r2.num))return true;else if (r1.sum2 / double(r1.num) == r2.sum2 / double(r2.num))return r1.min_id < r2.min_id;elsereturn false;
}int find(int p)
{if (p != f[p]) f[p] = find(f[p]);return f[p];
}int main()
{cin >> N;int id1, id2, id3, k;for (int i = 0;i < N;i++){cin >> id1 >> id2 >> id3;cv.push_back(id1);rea[id1] = 1;if (id2 != -1){v[id1].push_back(id2);rea[id2] = 1;}if (id3 != -1){v[id1].push_back(id3);rea[id3] = 1;}cin >> k;while (k--){int child;cin >> child;v[id1].push_back(child);}cin >> value[id1].set >> value[id1].area;}for (int i = 0;i < 10000;i++)f[i] = i;for (int i = 0;i < cv.size();i++){for (int j = 0;j < v[cv[i]].size();j++){int a = find(cv[i]), b = find(v[cv[i]][j]);if (a != b) f[b] = a;}}map<int, results> R1;for (int i = 0;i < 10000;i++){if (i < R1[find(i)].min_id)R1[find(i)].min_id = i;R1[find(i)].num++;R1[find(i)].sum1 += value[i].set;R1[find(i)].sum2 += value[i].area;}for (int i = 0;i < 10000;i++){if ((R1[find(i)].num >= 2 || (R1[find(i)].num == 1 && rea[i]))&&R1[find(i)].tag==0){R.push_back(R1[find(i)]);R1[find(i)].tag = 1;}}sort(R.begin(), R.end(), comp);cout << R.size() << endl;for (auto i : R)cout << setw(4) << setfill('0') << i.min_id << " " << i.num << " " << fixed << setprecision(3) << i.sum1 / double(i.num) << " " << fixed << setprecision(3) << i.sum2 / double(i.num) << endl;
}