liuchuo – 第203页

1079. Total Sales of Supply Chain (25)-PAT甲级真题（dfs,bfs,树的遍历）

A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.

Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.

Now given a supply chain, you are supposed to tell the total sales from all the retailers.

Input Specification:

Each input file contains one test case. For each case, the first line contains three positive numbers: N (<=105), the total number of the members in the supply chain (and hence their ID’s are numbered from 0 to N-1, and the root supplier’s ID is 0); P, the unit price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:

Ki ID[1] ID[2] … ID[Ki]

where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID’s of these distributors or retailers. Kj being 0 means that the j-th member is a retailer, then instead the total amount of the product will be given after Kj. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the total sales we can expect from all the retailers, accurate up to 1 decimal place. It is guaranteed that the number will not exceed 1010.

Sample Input:
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
Sample Output:
42.4

题目大意：给一棵树，在树根出货物的价格为p，然后从根结点开始每往下走一层，该层的货物价格将会在父亲结点的价格上增加r%，给出每个叶结点的货物量，求他们的价格之和
分析：树的遍历，可以采用dfs或者bfs两种方法。
采用dfs，建立结构体数组保存每一个结点的孩子结点的下标，如果没有孩子结点，就保存这个叶子结点的data（销售的量）。深度优先遍历的递归出口，即当前下标的结点没有孩子结点的时候，就把ans += data（货物量）* pow(1 + r, depth)计算货物量*价格引起的涨幅百分比。如果有孩子结点，就dfs深度优先遍历每一个孩子结点，并且在当前depth层数的基础上+1。最后输出ans * p（销售价格），即总价格

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
struct node {
    double data;
    vector<int> child;
};
vector<node> v;
double ans = 0.0, p, r;

void dfs(int index, int depth) {
    if(v[index].child.size() == 0) {
        ans += v[index].data * pow(1 + r, depth);
        return ;
    }
    for(int i = 0; i < v[index].child.size(); i++)
        dfs(v[index].child[i], depth + 1);
}
int main() {
    int n, k, c;
    scanf("%d %lf %lf", &n, &p, &r);
    r = r / 100;
    v.resize(n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &k);
        if(k == 0) {
            scanf("%lf", &v[i].data);
        } else {
            for(int j = 0; j < k; j++) {
                scanf("%d", &c);
                v[i].child.push_back(c);
            }
        }
    }
    dfs(0, 0);
    printf("%.1f", ans * p);
    return 0;
}

#include <cstdio>

#include <vector>

#include <cmath>

using namespace std;

struct node {

double data;

vector<int> child;

};

vector<node> v;

double ans = 0.0, p, r;

void dfs(int index, int depth) {

if(v[index].child.size() == 0) {

ans += v[index].data * pow(1 + r, depth);

return ;

}

for(int i = 0; i < v[index].child.size(); i++)

dfs(v[index].child[i], depth + 1);

}

int main() {

int n, k, c;

scanf("%d %lf %lf", &n, &p, &r);

r = r / 100;

v.resize(n);

for(int i = 0; i < n; i++) {

scanf("%d", &k);

if(k == 0) {

scanf("%lf", &v[i].data);

} else {

for(int j = 0; j < k; j++) {

scanf("%d", &c);

v[i].child.push_back(c);

}

dfs(0, 0);

printf("%.1f", ans * p);

return 0;

}

iOS开发之touchesCancelled

touchesCancelled:

override func touchesCancelled(touches: Set<UITouch>?, withEvent event: UIEvent?) {
        
    }

override func touchesCancelled(touches: Set<UITouch>?, withEvent event: UIEvent?) {

}

当我们正在触摸屏幕的时候，如果出现了低电量、有电话呼入等等这样的系统事件时候，低电量或者电话的窗口会置为前台，这个时候touchesCancelled方法就会被调用。

因为在软件运行过程中不可避免的会发生由iOS系统发出的一些事件，导致触摸事件的中断，所以一般建议要实现touchesCancelled这个方法，一般情况下直接调用touchesEnd即可。

touchesCancelled：Sent to the responder when a system event (such as a low-memory warning) cancels a touch event.

1012. The Best Rank (25)-PAT甲级真题

To evaluate the performance of our first year CS majored students, we consider their grades of three courses only: C – C Programming Language, M – Mathematics (Calculus or Linear Algebra), and E – English. At the mean time, we encourage students by emphasizing on their best ranks — that is, among the four ranks with respect to the three courses and the average grade, we print the best rank for each student.

For example, The grades of C, M, E and A – Average of 4 students are given as the following:

StudentID C M E A
310101 98 85 88 90
310102 70 95 88 84
310103 82 87 94 88
310104 91 91 91 91
Then the best ranks for all the students are No.1 since the 1st one has done the best in C Programming Language, while the 2nd one in Mathematics, the 3rd one in English, and the last one in average.

Input

Each input file contains one test case. Each case starts with a line containing 2 numbers N and M (<=2000), which are the total number of students, and the number of students who would check their ranks, respectively. Then N lines follow, each contains a student ID which is a string of 6 digits, followed by the three integer grades (in the range of [0, 100]) of that student in the order of C, M and E. Then there are M lines, each containing a student ID.

Output

For each of the M students, print in one line the best rank for him/her, and the symbol of the corresponding rank, separated by a space.

The priorities of the ranking methods are ordered as A > C > M > E. Hence if there are two or more ways for a student to obtain the same best rank, output the one with the highest priority.

If a student is not on the grading list, simply output “N/A”.

Sample Input
5 6
310101 98 85 88
310102 70 95 88
310103 82 87 94
310104 91 91 91
310105 85 90 90
310101
310102
310103
310104
310105
999999
Sample Output
1 C
1 M
1 E
1 A
3 A
N/A

题目大意：现已知n个考生的3门分数，平均分可以按照这三门算出来。然后分别对这四个分数从高到低排序，这样对每个考生来说有4个排名。k个查询，对于每一个学生id，输出当前id学生的最好的排名和它对应的分数，如果名次相同，按照A>C>M>E的顺序输出～如果当前id不存在，输出N/A～
分析：
1、用结构体存储学生的id、四门成绩、四门排名、最好的排名的对应的科目下标～
2、排名并列应该1、1、3、4、5，而不是1、1、2、3、4，否则会有一个测试点不过
3、平均分是四舍五入的，所以需要按照+0.5后取整，保证是四舍五入的（听说不四舍五入也能通过…）
4、存储的时候就按照ACME的顺序存储可以简化程序逻辑～
5、用exist数组保存当前id是否存在，这个id对应的stu结构体的下标是多少。用i+1可以保证为0的都是不存在的可以直接输出N/A，其余不为0的保存的值是对应的结构体index + 1的值～

#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
    int id, best;
    int score[4], rank[4];
}stu[2005];
int exist[1000000], flag = -1;
bool cmp1(node a, node b) {return a.score[flag] > b.score[flag];}
int main() {
    int n, m, id;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &stu[i].id, &stu[i].score[1], &stu[i].score[2], &stu[i].score[3]);
        stu[i].score[0] = (stu[i].score[1] + stu[i].score[2] + stu[i].score[3]) / 3.0 + 0.5;
    }
    for(flag = 0; flag <= 3; flag++) {
        sort(stu, stu + n, cmp1);
        stu[0].rank[flag] = 1;
        for(int i = 1; i < n; i++) {
            stu[i].rank[flag] = i + 1;
            if(stu[i].score[flag] == stu[i-1].score[flag])
                stu[i].rank[flag] = stu[i-1].rank[flag];
        }
    }
    for(int i = 0; i < n; i++) {
        exist[stu[i].id] = i + 1;
        stu[i].best = 0;
        int minn = stu[i].rank[0];
        for(int j = 1; j <= 3; j++) {
            if(stu[i].rank[j] < minn) {
                minn = stu[i].rank[j];
                stu[i].best = j;
            }
        }
    }
    char c[5] = {'A', 'C', 'M', 'E'};
    for(int i = 0; i < m; i++) {
        scanf("%d", &id);
        int temp = exist[id];
        if(temp) {
            int best = stu[temp-1].best;
            printf("%d %c\n", stu[temp-1].rank[best], c[best]);
        } else {
            printf("N/A\n");
        }
    }
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

struct node {

int id, best;

int score[4], rank[4];

}stu[2005];

int exist[1000000], flag = -1;

bool cmp1(node a, node b) {return a.score[flag] > b.score[flag];}

int main() {

int n, m, id;

scanf("%d %d", &n, &m);

for(int i = 0; i < n; i++) {

scanf("%d %d %d %d", &stu[i].id, &stu[i].score[1], &stu[i].score[2], &stu[i].score[3]);

stu[i].score[0] = (stu[i].score[1] + stu[i].score[2] + stu[i].score[3]) / 3.0 + 0.5;

}

for(flag = 0; flag <= 3; flag++) {

sort(stu, stu + n, cmp1);

stu[0].rank[flag] = 1;

for(int i = 1; i < n; i++) {

stu[i].rank[flag] = i + 1;

if(stu[i].score[flag] == stu[i-1].score[flag])

stu[i].rank[flag] = stu[i-1].rank[flag];

}

for(int i = 0; i < n; i++) {

exist[stu[i].id] = i + 1;

stu[i].best = 0;

int minn = stu[i].rank[0];

for(int j = 1; j <= 3; j++) {

if(stu[i].rank[j] < minn) {

minn = stu[i].rank[j];

stu[i].best = j;

}

char c[5] = {'A', 'C', 'M', 'E'};

for(int i = 0; i < m; i++) {

scanf("%d", &id);

int temp = exist[id];

if(temp) {

int best = stu[temp-1].best;

printf("%d %c\n", stu[temp-1].rank[best], c[best]);

} else {

printf("N/A\n");

}

return 0;

}

1082. Read Number in Chinese (25)-PAT甲级真题

Given an integer with no more than 9 digits, you are supposed to read it in the traditional Chinese way. Output “Fu” first if it is negative. For example, -123456789 is read as “Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu”. Note: zero (“ling”) must be handled correctly according to the Chinese tradition. For example, 100800 is “yi Shi Wan ling ba Bai”.
Input Specification:
Each input file contains one test case, which gives an integer with no more than 9 digits.
Output Specification:
For each test case, print in a line the Chinese way of reading the number. The characters are separated by a space and there must be no extra space at the end of the line.
Sample Input 1:
-123456789
Sample Output 1:
Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu
Sample Input 2:
100800
Sample Output 2:
yi Shi Wan ling ba Bai

题目大意：给定一个不超过9位的整数，你应该用传统的中文方式阅读它~ 如果是负的，首先输出“Fu”。例如，-123456789被读作“Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu”。注意：零（“ling”）必须根据中国传统正确处理。例如，100800是“yi Shi Wan ling ba Bai”~

#include <iostream>
#include <string>
#include <vector>
using namespace std;
string num[10] = { "ling","yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu" };
string c[6] = { "Ge","Shi", "Bai", "Qian", "Yi", "Wan" };
int J[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
vector<string> res;
int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << "ling";
        return 0;
    }
    if (n < 0) {
        cout << "Fu ";
        n = -n;
    }
    int part[3];
    part[0]= n / 100000000; 
    part[1]= (n % 100000000) / 10000;
    part[2] = n % 10000;
    bool zero = false; //是否在非零数字前输出合适的ling
    int printCnt = 0; //用于维护单词前没有空格，之后输入的单词都在前面加一个空格。
    for (int i = 0; i < 3; i++) {
        int temp = part[i]; //三个部分，每部分内部的命名规则都一样，都是X千X百X十X
        for (int j = 3; j >= 0; j--) {
            int curPos = 8 - i * 4 + j; //当前数字的位置
            if (curPos >= 9) continue; //最多九位数
            int cur = (temp / J[j]) % 10;//取出当前数字
            if (cur != 0) {
                if (zero) {
                    printCnt++ == 0 ? cout<<"ling" : cout<<" ling";
                    zero = false;
                }
                if (j == 0)
                    printCnt++ == 0 ? cout << num[cur] : cout << ' ' << num[cur]; //在个位，直接输出
                else                             
                    printCnt++ == 0 ? cout << num[cur] << ' ' << c[j] : cout << ' ' << num[cur] << ' ' << c[j]; //在其他位，还要输出十百千
            } else {
                if (!zero && j != 0 && n / J[curPos] >= 10) zero = true;   //注意100020这样的情况
            }
        }
        if (i != 2 && part[i]>0) cout << ' ' << c[i + 4]; //处理完每部分之后，最后输出单位，Yi/Wan
    }
    return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

string num[10] = { "ling","yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu" };

string c[6] = { "Ge","Shi", "Bai", "Qian", "Yi", "Wan" };

int J[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};

vector<string> res;

int main() {

int n;

cin >> n;

if (n == 0) {

cout << "ling";

return 0;

}

if (n < 0) {

cout << "Fu ";

n = -n;

}

int part[3];

part[0]= n / 100000000;

part[1]= (n % 100000000) / 10000;

part[2] = n % 10000;

bool zero = false; //是否在非零数字前输出合适的ling

int printCnt = 0; //用于维护单词前没有空格，之后输入的单词都在前面加一个空格。

for (int i = 0; i < 3; i++) {

int temp = part[i]; //三个部分，每部分内部的命名规则都一样，都是X千X百X十X

for (int j = 3; j >= 0; j--) {

int curPos = 8 - i * 4 + j; //当前数字的位置

if (curPos >= 9) continue; //最多九位数

int cur = (temp / J[j]) % 10;//取出当前数字

if (cur != 0) {

if (zero) {

printCnt++ == 0 ? cout<<"ling" : cout<<" ling";

zero = false;

}

if (j == 0)

printCnt++ == 0 ? cout << num[cur] : cout << ' ' << num[cur]; //在个位，直接输出

else

printCnt++ == 0 ? cout << num[cur] << ' ' << c[j] : cout << ' ' << num[cur] << ' ' << c[j]; //在其他位，还要输出十百千

} else {

if (!zero && j != 0 && n / J[curPos] >= 10) zero = true; //注意100020这样的情况

}

if (i != 2 && part[i]>0) cout << ' ' << c[i + 4]; //处理完每部分之后，最后输出单位，Yi/Wan

}

return 0;

}

1114. Family Property (25)-PAT甲级真题（并查集）

This time, you are supposed to help us collect the data for family-owned property. Given each person’s family members, and the estate（房产）info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000). Then N lines follow, each gives the infomation of a person who owns estate in the format:

ID Father Mother k Child1 … Childk M_estate Area

where ID is a unique 4-digit identification number for each person; Father and Mother are the ID’s of this person’s parents (if a parent has passed away, -1 will be given instead); k (0<=k<=5) is the number of children of this person; Childi’s are the ID’s of his/her children; M_estate is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.

Output Specification:

For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format:

ID M AVG_sets AVG_area

where ID is the smallest ID in the family; M is the total number of family members; AVG_sets is the average number of sets of their real estate; and AVG_area is the average area. The average numbers must be accurate up to 3 decimal places. The families must be given in descending order of their average areas, and in ascending order of the ID’s if there is a tie.

Sample Input:
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100
Sample Output:
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

题目大意：给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：家庭成员的最小编号家庭人口数人均房产套数人均房产面积。其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
分析：用并查集。分别用两个结构体数组，一个data用来接收数据，接收的时候顺便实现了并查集的操作union，另一个数组ans用来输出最后的答案，因为要计算家庭人数，所以用visit标记所有出现过的结点，对于每个结点的父结点，people++统计人数。标记flag == true，计算true的个数cnt就可以知道一共有多少个家庭。排序后输出前cnt个就是所求答案～～

#include <cstdio>
#include <algorithm>
using namespace std;
struct DATA {
    int id, fid, mid, num, area;
    int cid[10];
}data[1005];
struct node {
    int id, people;
    double num, area;
    bool flag = false;
}ans[10000];
int father[10000];
bool visit[10000];
int find(int x) {
    while(x != father[x])
        x = father[x];
    return x;
}
void Union(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    if(faA > faB)
        father[faA] = faB;
    else if(faA < faB)
        father[faB] = faA;
}
int cmp1(node a, node b) {
    if(a.area != b.area)
        return a.area > b.area;
    else
        return a.id < b.id;
}
int main() {
    int n, k, cnt = 0;
    scanf("%d", &n);
    for(int i = 0; i < 10000; i++)
        father[i] = i;
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &data[i].id, &data[i].fid, &data[i].mid, &k);
        visit[data[i].id] = true;
        if(data[i].fid != -1) {
            visit[data[i].fid] = true;
            Union(data[i].fid, data[i].id);
        }
        if(data[i].mid != -1) {
            visit[data[i].mid] = true;
            Union(data[i].mid, data[i].id);
        }
        for(int j = 0; j < k; j++) {
            scanf("%d", &data[i].cid[j]);
            visit[data[i].cid[j]] = true;
            Union(data[i].cid[j], data[i].id);
        }
        scanf("%d %d", &data[i].num, &data[i].area);
    }
    for(int i = 0; i < n; i++) {
        int id = find(data[i].id);
        ans[id].id = id;
        ans[id].num += data[i].num;
        ans[id].area += data[i].area;
        ans[id].flag = true;
    }
    for(int i = 0; i < 10000; i++) {
        if(visit[i])
            ans[find(i)].people++;
        if(ans[i].flag)
            cnt++;
    }
    for(int i = 0; i < 10000; i++) {
        if(ans[i].flag) {
            ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);
            ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);
        }
    }
    sort(ans, ans + 10000, cmp1);
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++)
        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

struct DATA {

int id, fid, mid, num, area;

int cid[10];

}data[1005];

struct node {

int id, people;

double num, area;

bool flag = false;

}ans[10000];

int father[10000];

bool visit[10000];

int find(int x) {

while(x != father[x])

x = father[x];

return x;

}

void Union(int a, int b) {

int faA = find(a);

int faB = find(b);

if(faA > faB)

father[faA] = faB;

else if(faA < faB)

father[faB] = faA;

}

int cmp1(node a, node b) {

if(a.area != b.area)

return a.area > b.area;

else

return a.id < b.id;

}

int main() {

int n, k, cnt = 0;

scanf("%d", &n);

for(int i = 0; i < 10000; i++)

father[i] = i;

for(int i = 0; i < n; i++) {

scanf("%d %d %d %d", &data[i].id, &data[i].fid, &data[i].mid, &k);

visit[data[i].id] = true;

if(data[i].fid != -1) {

visit[data[i].fid] = true;

Union(data[i].fid, data[i].id);

}

if(data[i].mid != -1) {

visit[data[i].mid] = true;

Union(data[i].mid, data[i].id);

}

for(int j = 0; j < k; j++) {

scanf("%d", &data[i].cid[j]);

visit[data[i].cid[j]] = true;

Union(data[i].cid[j], data[i].id);

}

scanf("%d %d", &data[i].num, &data[i].area);

}

for(int i = 0; i < n; i++) {

int id = find(data[i].id);

ans[id].id = id;

ans[id].num += data[i].num;

ans[id].area += data[i].area;

ans[id].flag = true;

}

for(int i = 0; i < 10000; i++) {

if(visit[i])

ans[find(i)].people++;

if(ans[i].flag)

cnt++;

}

for(int i = 0; i < 10000; i++) {

if(ans[i].flag) {

ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);

ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);

}

sort(ans, ans + 10000, cmp1);

printf("%d\n", cnt);

for(int i = 0; i < cnt; i++)

printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);

return 0;

}

L2-007. 家庭房产-PAT团体程序设计天梯赛GPLT

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。

输入格式：

输入第一行给出一个正整数N（<=1000），随后N行，每行按下列格式给出一个人的房产：

编号父母 k 孩子1 … 孩子k 房产套数总面积

其中编号是每个人独有的一个4位数的编号；父和母分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0<=k<=5）是该人的子女的个数；孩子i是其子女的编号。

输出格式：

首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：

家庭成员的最小编号家庭人口数人均房产套数人均房产面积

其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。

输入样例：
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100
输出样例：
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

分析：用并查集。分别用两个结构体数组，一个data用来接收数据，接收的时候顺便实现了并查集的操作union，另一个数组ans用来输出最后的答案，因为要计算家庭人数，所以用visit标记所有出现过的结点，对于每个结点的父结点，people++统计人数。标记flag == true，计算true的个数cnt就可以知道一共有多少个家庭。排序后输出前cnt个就是所求答案～～

#include <cstdio>
#include <algorithm>
using namespace std;
struct DATA {
    int id, fid, mid, num, area;
    int cid[10];
}data[1005];
struct node {
    int id, people;
    double num, area;
    bool flag = false;
}ans[10000];
int father[10000];
bool visit[10000];
int find(int x) {
    while(x != father[x])
        x = father[x];
    return x;
}
void Union(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    if(faA > faB)
        father[faA] = faB;
    else if(faA < faB)
        father[faB] = faA;
}
int cmp1(node a, node b) {
    if(a.area != b.area)
        return a.area > b.area;
    else
        return a.id < b.id;
}
int main() {
    int n, k, cnt = 0;
    scanf("%d", &n);
    for(int i = 0; i < 10000; i++)
        father[i] = i;
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &data[i].id, &data[i].fid, &data[i].mid, &k);
        visit[data[i].id] = true;
        if(data[i].fid != -1) {
            visit[data[i].fid] = true;
            Union(data[i].fid, data[i].id);
        }
        if(data[i].mid != -1) {
            visit[data[i].mid] = true;
            Union(data[i].mid, data[i].id);
        }
        for(int j = 0; j < k; j++) {
            scanf("%d", &data[i].cid[j]);
            visit[data[i].cid[j]] = true;
            Union(data[i].cid[j], data[i].id);
        }
        scanf("%d %d", &data[i].num, &data[i].area);
    }
    for(int i = 0; i < n; i++) {
        int id = find(data[i].id);
        ans[id].id = id;
        ans[id].num += data[i].num;
        ans[id].area += data[i].area;
        ans[id].flag = true;
    }
    for(int i = 0; i < 10000; i++) {
        if(visit[i])
            ans[find(i)].people++;
        if(ans[i].flag)
            cnt++;
    }
    for(int i = 0; i < 10000; i++) {
        if(ans[i].flag) {
            ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);
            ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);
        }
    }
    sort(ans, ans + 10000, cmp1);
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++)
        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

struct DATA {

int id, fid, mid, num, area;

int cid[10];

}data[1005];

struct node {

int id, people;

double num, area;

bool flag = false;

}ans[10000];

int father[10000];

bool visit[10000];

int find(int x) {

while(x != father[x])

x = father[x];

return x;

}

void Union(int a, int b) {

int faA = find(a);

int faB = find(b);

if(faA > faB)

father[faA] = faB;

else if(faA < faB)

father[faB] = faA;

}

int cmp1(node a, node b) {

if(a.area != b.area)

return a.area > b.area;

else

return a.id < b.id;

}

int main() {

int n, k, cnt = 0;

scanf("%d", &n);

for(int i = 0; i < 10000; i++)

father[i] = i;

for(int i = 0; i < n; i++) {

scanf("%d %d %d %d", &data[i].id, &data[i].fid, &data[i].mid, &k);

visit[data[i].id] = true;

if(data[i].fid != -1) {

visit[data[i].fid] = true;

Union(data[i].fid, data[i].id);

}

if(data[i].mid != -1) {

visit[data[i].mid] = true;

Union(data[i].mid, data[i].id);

}

for(int j = 0; j < k; j++) {

scanf("%d", &data[i].cid[j]);

visit[data[i].cid[j]] = true;

Union(data[i].cid[j], data[i].id);

}

scanf("%d %d", &data[i].num, &data[i].area);

}

for(int i = 0; i < n; i++) {

int id = find(data[i].id);

ans[id].id = id;

ans[id].num += data[i].num;

ans[id].area += data[i].area;

ans[id].flag = true;

}

for(int i = 0; i < 10000; i++) {

if(visit[i])

ans[find(i)].people++;

if(ans[i].flag)

cnt++;

}

for(int i = 0; i < 10000; i++) {

if(ans[i].flag) {

ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);

ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);

}

sort(ans, ans + 10000, cmp1);

printf("%d\n", cnt);

for(int i = 0; i < cnt; i++)

printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);

return 0;

}