题解 | #【模板】有依赖的背包问题#

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int n; vector<int> fa, sz;
    DSU(int n): n(n), fa(n+1), sz(n+1,1) { iota(fa.begin(), fa.end(), 0); }
    int find(int x){ return fa[x]==x? x: fa[x]=find(fa[x]); }
    void unite(int a,int b){ a=find(a); b=find(b); if(a==b) return; if(sz[a]<sz[b]) swap(a,b); fa[b]=a; sz[a]+=sz[b]; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, K; if(!(cin >> n >> m >> K)) return 0;
    vector<int> price(n+1), value(n+1);
    for(int i=1;i<=n;i++) cin >> price[i] >> value[i];
    DSU dsu(n);
    for(int i=0;i<m;i++){ int u,v; cin >> u >> v; dsu.unite(u,v); }

    vector<long long> W(n+1,0), V(n+1,0);
    for(int i=1;i<=n;i++){ int r=dsu.find(i); W[r]+=price[i]; V[r]+=value[i]; }
    vector<int> itemsW, itemsV;
    for(int i=1;i<=n;i++) if(dsu.find(i)==i){ itemsW.push_back((int)W[i]); itemsV.push_back((int)V[i]); }

    vector<long long> dp(K+1, 0);
    for(size_t i=0;i<itemsW.size();i++){
        int w = itemsW[i], v = itemsV[i];
        for(int j=K;j>=w;j--) dp[j] = max(dp[j], dp[j-w] + v);
    }
    cout << dp[K] << '\n';
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        private final InputStream in; private final byte[] buf = new byte[1<<16];
        private int p=0,l=0; FastScanner(InputStream is){in=is;}
        private int read() throws IOException { if(p>=l){ l=in.read(buf); p=0; if(l<=0) return -1; } return buf[p++]; }
        int nextInt() throws IOException { int c; int s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
    }

    static class DSU {
        int[] fa, sz;
        DSU(int n){ fa=new int[n+1]; sz=new int[n+1]; for(int i=0;i<=n;i++){ fa[i]=i; sz[i]=1; } }
        int find(int x){ return fa[x]==x? x: (fa[x]=find(fa[x])); }
        void unite(int a,int b){ a=find(a); b=find(b); if(a==b) return; if(sz[a]<sz[b]){int t=a;a=b;b=t;} fa[b]=a; sz[a]+=sz[b]; }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();
        int K = fs.nextInt();
        int[] price = new int[n+1];
        int[] value = new int[n+1];
        for(int i=1;i<=n;i++){ price[i]=fs.nextInt(); value[i]=fs.nextInt(); }
        DSU dsu = new DSU(n);
        for(int i=0;i<m;i++){ int u=fs.nextInt(), v=fs.nextInt(); dsu.unite(u,v); }

        long[] W = new long[n+1];
        long[] V = new long[n+1];
        for(int i=1;i<=n;i++){ int r=dsu.find(i); W[r]+=price[i]; V[r]+=value[i]; }
        ArrayList<Integer> wList = new ArrayList<>();
        ArrayList<Integer> vList = new ArrayList<>();
        for(int i=1;i<=n;i++) if(dsu.find(i)==i){ wList.add((int)W[i]); vList.add((int)V[i]); }

        long[] dp = new long[K+1];
        for(int idx=0; idx<wList.size(); idx++){
            int w = wList.get(idx), v = vList.get(idx);
            for(int j=K; j>=w; j--) dp[j] = Math.max(dp[j], dp[j-w] + v);
        }
        System.out.println(dp[K]);
    }
}

import sys

data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it)); m = int(next(it)); K = int(next(it))
price = [0]*(n+1)
value = [0]*(n+1)
for i in range(1, n+1):
    price[i] = int(next(it)); value[i] = int(next(it))

fa = list(range(n+1))
sz = [1]*(n+1)
def find(x: int) -> int:
    while fa[x] != x:
        fa[x] = fa[fa[x]]
        x = fa[x]
    return x
def unite(a: int, b: int):
    ra, rb = find(a), find(b)
    if ra == rb: return
    if sz[ra] < sz[rb]:
        ra, rb = rb, ra
    fa[rb] = ra
    sz[ra] += sz[rb]

for _ in range(m):
    u = int(next(it)); v = int(next(it))
    unite(u, v)

W = [0]*(n+1)
V = [0]*(n+1)
for i in range(1, n+1):
    r = find(i)
    W[r] += price[i]
    V[r] += value[i]

items = [(W[i], V[i]) for i in range(1, n+1) if find(i) == i]
dp = [0]*(K+1)
for w, v in items:
    if w > K: continue
    for j in range(K, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)
print(dp[K])