代码如下:
import sys
input = lambda: sys.stdin.readline().strip()
def find(x, s):
if x != s[x]:
s[x] = find(s[x], s)
return s[x]
def merge(x, y, s):
x = find(x, s)
y = find(y, s)
if x != y:
s[x] = s[y]
def initial(n, m, cloud, new_cloud, s):
for _ in range(n):
cloud.append(list(map(int, input().split())))
for _ in range(m):
x, y = map(int, input().split())
merge(x, y, s)
for i in range(1, n + 1):
find(i, s)
S = list(set(s[1:]))
for i in S:
new_cloud[i] = [0, 0]
for i in range(1, n + 1):
j = find(i, s)
new_cloud[j][0] += cloud[i - 1][0]
new_cloud[j][1] += cloud[i - 1][1]
def solve(w, new_cloud):
dp = [0] * (w + 1)
for i in new_cloud:
for j in range(w, new_cloud[i][0] - 1, -1):
dp[j] = max(dp[j], dp[j - new_cloud[i][0]] + new_cloud[i][1])
print(dp[w])
def main():
n, m, w = map(int, input().split())
s = [i for i in range(n + 1)]
cloud = []
new_cloud = {}
initial(n, m, cloud, new_cloud, s)
solve(w, new_cloud)
main()
实在是不知道怎么改了