SHARE
TWEET

Untitled

a guest Aug 23rd, 2019 104 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayList;
  4. import java.util.Collections;
  5.  
  6. public class nccc2s51 {
  7.     public static class Edge1 {
  8.         int ev, cost;
  9.         public Edge1(int ev, int cost) {
  10.             this.ev = ev; this.cost = cost;
  11.         }
  12.     }
  13.  
  14.     public static class Edge implements Comparable<Edge> {
  15.         public int bv;
  16.         public int ev;
  17.         public int cost;
  18.         public Edge(int bv, int ev, int cost) {
  19.             this.bv = bv;
  20.             this.ev = ev;
  21.             this.cost = cost;
  22.         }
  23.         @Override
  24.         public int compareTo(Edge o) {
  25.             // TODO Auto-generated method stub
  26.             return o.cost-this.cost;
  27.         }  
  28.     }
  29.     public static ArrayList<Edge> edges;
  30.     public static ArrayList<Edge> temp;
  31.     public static int V;
  32.     public static int E;
  33.     public static int[] parent;
  34.     public static int[] rank;
  35.     public static ArrayList<Edge1>[] adj;
  36.     public static int bsearch(int l, int r, Edge v) {
  37.         while(l <= r) {
  38.             int mid = (l+r)/2;
  39.             if(temp.get(mid).cost > v.cost) l=mid+1;
  40.             else if(temp.get(mid).cost < v.cost) r = mid-1;
  41.             else {
  42.                 if(temp.get(mid).cost > v.cost) r = mid-1;
  43.                 else if(temp.get(mid).cost < v.cost) l = mid+1;
  44.                 return mid;
  45.             }
  46.         }
  47.         return l;
  48.     }
  49.    
  50.     public static void update() {
  51.         parent = new int[V+1]; rank = new int[V+1]; adj = new ArrayList[V+1];
  52.         for(int j=1;j<=N;j++) {
  53.             adj[j] = new ArrayList<p>();
  54.             make(j);
  55.         }
  56.         mst();
  57.     }
  58.     public static void main(String[] args) throws Exception {
  59.         BufferedReader br = new BufferedReader(
  60.                         new InputStreamReader(System.in));
  61.         String[] A = br.readLine().split(" ");
  62.         V = Integer.parseInt(A[0]);
  63.         E = Integer.parseInt(A[1]);
  64.         edges = new ArrayList<Edge>();
  65.         for(int i=0;i<E;i++) {
  66.             A = br.readLine().split(" ");
  67.             int bv = Integer.parseInt(A[0]);
  68.             int ev = Integer.parseInt(A[1]);
  69.             int cost = Integer.parseInt(A[2]);;
  70.             edges.add(new Edge(bv, ev, cost));
  71.         }
  72.         temp = new ArrayList<Edge>(edges);
  73.         Collections.sort(temp);
  74.        
  75.         int Q = Integer.parseInt(br.readLine());
  76.         for(int i=0;i<Q;i++) {
  77.             A = br.readLine().split(" ");
  78.             int op = Integer.parseInt(A[0]);
  79.             if(op == 1) {
  80.                 int m = Integer.parseInt(A[1]);
  81.                 int x = Integer.parseInt(A[2]);
  82.                 Edge r = edges.remove(m-1);   //original edge
  83.                 Edge r2 = new Edge(r.bv,r.ev,x);   //new edge
  84.                 edges.add(m-1, r2);
  85.                 int ind = bsearch(0, E-1, r);   //from temp original edge location
  86.                 temp.remove(ind);
  87.                 ind = bsearch(0, E-2, r2);
  88.                 temp.add(ind, r2);
  89.                 update();   //max spaning tree
  90.                 // System.out.println("update check: " + edges.get(m-1).x + " " + edges.get(m-1).y + " " + edges.get(m-1).z);
  91.             }
  92.        
  93.     }
  94.  
  95. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top