Advertisement
Guest User

Untitled

a guest
Oct 20th, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.89 KB | None | 0 0
  1. import java.math.*;
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class Main{
  6.     public static void main(String[] args ) throws IOException{
  7.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  8.                 String[] in = br.readLine().split(" ");
  9.                 int n = Integer.parseInt(in[0]);
  10.                 int m = Integer.parseInt(in[1]);
  11.                 int w = Integer.parseInt(in[2]);
  12.                 set = new int[n];
  13.                 for( int i = 0; i < n; i++)
  14.                     set[i] = i;
  15.  
  16.                 in = br.readLine().split(" ");
  17.                 int[] weights = new int[n];
  18.                 for(int i = 0; i < n; i++){
  19.                     weights[i] = Integer.parseInt(in[i]);
  20.                 }
  21.                 int[] beauty = new int[n];
  22.                 in = br.readLine().split(" ");
  23.                 for( int i = 0; i < n; i++){
  24.                     beauty[i] = Integer.parseInt(in[i]);
  25.                 }
  26.                 for( int i = 0; i < m; i++){
  27.                     in = br.readLine().split(" ");
  28.                     int a = Integer.parseInt(in[0]) -1;
  29.                     int b = Integer.parseInt(in[1]) -1;
  30.                     union(a,b);
  31.                 }
  32.  
  33.                 ArrayList<ArrayList<Integer>> sets = new ArrayList<>();
  34.                 boolean[] used = new boolean[n];
  35.                 for( int i =0; i < n; i++){
  36.                     int root = find(i);
  37.                     if(used[root])continue;
  38.                     used[root] = true;
  39.                     ArrayList<Integer> list = new ArrayList<>();
  40.                     list.add(i);
  41.                    
  42.                     for( int j = i+1; j < n; j++){
  43.                         if(find(j) == root){
  44.                             list.add(j);
  45.                         }
  46.                     }
  47.                     sets.add(list);
  48.                 }
  49.  
  50.                 int[][] dp = new int[sets.size()+1][w+1];
  51.                 for( int i = 0; i < sets.size()+1; i++){
  52.                     for( int j = 0; j < w+1; j++){
  53.                         dp[i][j] = -1;
  54.                     }
  55.                 }
  56.                 dp[0][0] = 0;
  57.                 for( int i = 0; i < sets.size(); i++){
  58.                     for( int j = 0; j <= w;j++){
  59.                         if(dp[i][j] == -1)
  60.                             continue;
  61.  
  62.                         ArrayList<Integer> list = sets.get(i);
  63.                         int sumWeights = 0;
  64.                         int sumBeauty = 0;
  65.                         for( int k = 0; k < list.size(); k++){
  66.                             int h = list.get(k);
  67.                             int weight = weights[h];
  68.                             int beau = beauty[h];
  69.                             sumWeights += weight;
  70.                             sumBeauty += beau;
  71.                             if(weight + j <= w){
  72.                                 dp[i+1][j + weight] = Math.max(dp[i+1][j + weight],
  73.                                         dp[i][j] + beau);
  74.                             }
  75.  
  76.                         }
  77.  
  78.                         if(sumWeights + j <= w){
  79.                             dp[i+1][j + sumWeights] = Math.max(dp[i+1][j + sumWeights],
  80.                                     dp[i][j] + sumBeauty);
  81.                         }
  82.                         dp[i+1][j] = Math.max(dp[i+1][j],
  83.                             dp[i][j]);
  84.                     }
  85.                 }
  86.                 int max = 0;
  87.                 for( int i = 0; i <= w; i++){
  88.                     max = Math.max(max,
  89.                             dp[sets.size()][i]);
  90.                 }
  91.                 System.out.println(max);
  92.  
  93.     }
  94.     static int set[];
  95.     public static void union(int s1, int s2) {
  96.         int a = find(s1);
  97.         int b = find(s2);
  98.         set[Math.min(a, b)] = Math.max(a, b);
  99.     }
  100.     public static int find(int index) {
  101.         if (set[index] == index)return index;
  102.         return set[index] = find(set[index]);
  103.     }
  104.  
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement