Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.math.*;
- import java.io.*;
- import java.util.*;
- public class Main{
- public static void main(String[] args ) throws IOException{
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- String[] in = br.readLine().split(" ");
- int n = Integer.parseInt(in[0]);
- int m = Integer.parseInt(in[1]);
- int w = Integer.parseInt(in[2]);
- set = new int[n];
- for( int i = 0; i < n; i++)
- set[i] = i;
- in = br.readLine().split(" ");
- int[] weights = new int[n];
- for(int i = 0; i < n; i++){
- weights[i] = Integer.parseInt(in[i]);
- }
- int[] beauty = new int[n];
- in = br.readLine().split(" ");
- for( int i = 0; i < n; i++){
- beauty[i] = Integer.parseInt(in[i]);
- }
- for( int i = 0; i < m; i++){
- in = br.readLine().split(" ");
- int a = Integer.parseInt(in[0]) -1;
- int b = Integer.parseInt(in[1]) -1;
- union(a,b);
- }
- ArrayList<ArrayList<Integer>> sets = new ArrayList<>();
- boolean[] used = new boolean[n];
- for( int i =0; i < n; i++){
- int root = find(i);
- if(used[root])continue;
- used[root] = true;
- ArrayList<Integer> list = new ArrayList<>();
- list.add(i);
- for( int j = i+1; j < n; j++){
- if(find(j) == root){
- list.add(j);
- }
- }
- sets.add(list);
- }
- int[][] dp = new int[sets.size()+1][w+1];
- for( int i = 0; i < sets.size()+1; i++){
- for( int j = 0; j < w+1; j++){
- dp[i][j] = -1;
- }
- }
- dp[0][0] = 0;
- for( int i = 0; i < sets.size(); i++){
- for( int j = 0; j <= w;j++){
- if(dp[i][j] == -1)
- continue;
- ArrayList<Integer> list = sets.get(i);
- int sumWeights = 0;
- int sumBeauty = 0;
- for( int k = 0; k < list.size(); k++){
- int h = list.get(k);
- int weight = weights[h];
- int beau = beauty[h];
- sumWeights += weight;
- sumBeauty += beau;
- if(weight + j <= w){
- dp[i+1][j + weight] = Math.max(dp[i+1][j + weight],
- dp[i][j] + beau);
- }
- }
- if(sumWeights + j <= w){
- dp[i+1][j + sumWeights] = Math.max(dp[i+1][j + sumWeights],
- dp[i][j] + sumBeauty);
- }
- dp[i+1][j] = Math.max(dp[i+1][j],
- dp[i][j]);
- }
- }
- int max = 0;
- for( int i = 0; i <= w; i++){
- max = Math.max(max,
- dp[sets.size()][i]);
- }
- System.out.println(max);
- }
- static int set[];
- public static void union(int s1, int s2) {
- int a = find(s1);
- int b = find(s2);
- set[Math.min(a, b)] = Math.max(a, b);
- }
- public static int find(int index) {
- if (set[index] == index)return index;
- return set[index] = find(set[index]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement