网站没有收录,义乌市网站制作,广州市建设工程检测中心网站,网站建设方案的摘要题目链接
思路#xff1a; 本题将每个人作为一个单独的结点#xff0c;若两个人之间是家人关系#xff0c;则建立边关系。通过哈希法建立人名与编号#xff0c;编号与人名之间的映射。最后统计每个家庭的人数时#xff0c;用DFS遍历即可。
对于本题我犯过两个错误#…题目链接
思路 本题将每个人作为一个单独的结点若两个人之间是家人关系则建立边关系。通过哈希法建立人名与编号编号与人名之间的映射。最后统计每个家庭的人数时用DFS遍历即可。
对于本题我犯过两个错误仅供读者参考 1.建立边关系的时候应当建立双向边而不是单向边。 2.出现的人数比较大数组开大一点。
参考代码
#includebits/stdc.h
#includeunordered_map
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;unordered_mapstring, int ConvertToInt; //形成人名与编号之间的映射
unordered_mapint, string ConvertToString; //形成编号与人名之间的映射
vectorint e[1005]; //建立图邻接表形式
int snum[1005] { 0 }, area[1005] { 0 }; //snum表示编号为i的人拥有的房屋数量 area同理bool vis[1005]; //表示dfs遍历种结点是否被访问过
int sumnum, sumarea, people; //表示在每轮dfs遍历中这个家庭的总房屋数总面积 总人数
string sumname; //表示在每轮dfs遍历中字典序最小的名字
void dfs(int index)
{vis[index] true;sumnum snum[index];sumarea area[index];people;if (ConvertToString[index] sumname)sumname ConvertToString[index];for (auto x : e[index]){if (vis[x] false)dfs(x);}
}struct node { //表示家庭信息的结构体string name;double num, area;int people;node(string a, double b, double c, int d) {name a, num b, area c, people d;;}
};bool cmp(node a, node b)
{if (a.area b.area) return a.name b.name;else return a.area b.area;
}int main()
{int n;cin n;int t 0;while (n--){string id, father, mother, child;int k, tnum, tarea;cin id father mother k;if (!ConvertToInt.count(id)){ConvertToInt[id] t;ConvertToString[t] id;t;}int top ConvertToInt[id];vectorstring v; //创建数组存放家人编号if (father ! -1) v.emplace_back(father);if (mother ! -1) v.emplace_back(mother);for (int i 0; i k;i){cin child;v.emplace_back(child);}for (auto name : v){if (!ConvertToInt.count(name)){ConvertToInt[name] t;ConvertToString[t] name;t;}e[top].emplace_back(ConvertToInt[name]);e[ConvertToInt[name]].emplace_back(top);}cin tnum tarea;snum[top] tnum; //存入房屋拥有者的房屋套数信息area[top] tarea; //存入房屋拥有者的房屋面积信息}vectornode res; //存放最终的家庭信息for (int i 0; i t;i)if (vis[i] false){sumarea 0, sumnum 0, people 0;sumname ConvertToString[i];dfs(i);res.push_back(node(sumname, 1.0 * sumnum / people, 1.0 * sumarea / people, people));}sort(res.begin(), res.end(), cmp); //按题目要求进行家庭排序cout res.size() endl;for (auto info : res){cout info.name;printf( %d %.3f %.3f\n, info.people, info.num, info.area);}return 0;
}
