并查集练习_AcWing 1604.家产
作者:
成理第一深情
,
2024-05-02 14:26:47
,
所有人可见
,
阅读 12
import sys
sys.setrecursionlimit(1000010)
input = sys.stdin.readline
def find(x):
if x != p[x]:
p[x] = find(p[x])
return p[x]
n = int(input())
p = [i for i in range(10000)]
area = [0 for _ in range(10000)]
cnt = [0 for _ in range(10000)]
st = set()
for _ in range(n):
a = list(map(int, input().strip().split()))
member = []
member.append(a[0])
st.add(a[0])
if a[1] != -1:
member.append(a[1])
st.add(a[1])
if a[2] != -1:
member.append(a[2])
st.add(a[2])
k = a[3]
for i in range(4, 4 + k):
member.append(a[i])
st.add(a[i])
# member.sort()
# print(member)
t = find(member[0])
# 最开始的祖宗节点维护这两个信息
# 如果出现一个id更小的祖宗节点,需要将信息传递给这个小的祖宗节点
cnt[t] += a[-2]
area[t] += a[-1]
for x in member[1:]:
if find(x) == t:
continue
if find(x) < t:
last_cnt = cnt[t]
last_area = area[t]
p[t] = find(x)
t = find(x)
cnt[t] += last_cnt
area[t] += last_area
elif find(x) > t:
cnt[t] += cnt[find(x)]
area[t] += area[find(x)]
p[find(x)] = t
# 因为t可能一直在变,因此不能在这里统计
# cnt[t] += a[-2]
# area[t] += a[-1]
number = [0 for _ in range(10000)]
for i in range(10000):
if i in st:
number[find(i)] += 1
# 验证一下样例
# if number[find(i)] == 15:
# print("Yes")
ans = []
for i in range(10000):
if number[i] != 0:
# print(i, number[i], cnt[i] / number[i], area[i] / number[i])
ans.append([i, number[i], cnt[i] / number[i], area[i] / number[i]])
ans.sort(key=lambda x: (-x[-1], x[0]))
print(len(ans))
for i in range(len(ans)):
a, b, c, d = ans[i]
print("{:04d} {} {:.3f} {:.3f}".format(a, b, c, d))