Python求助贴,用了并查集和01背包,3TLE,1RE
查看原帖
Python求助贴,用了并查集和01背包,3TLE,1RE
1077867
SwordRain楼主2023/12/20 11:22

代码如下:

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()

实在是不知道怎么改了

2023/12/20 11:22
加载中...