Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.96 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.HashMap;
  5. import java.util.LinkedList;
  6. import java.util.Scanner;
  7.  
  8. public class ccc10s4
  9. {
  10. public static int[] parent;
  11. public static class Edge implements Comparable<Edge> {
  12. public int bv;
  13. public int ev;
  14. public int cost;
  15. public Edge(int bv, int ev, int cost) {
  16. this.bv = bv;
  17. this.ev = ev;
  18. this.cost = cost;
  19. }
  20. @Override
  21. public int compareTo(Edge o) {
  22. // TODO Auto-generated method stub
  23. return this.cost-o.cost;
  24. }
  25. }
  26. public static void main(String[] args)
  27. {
  28. Scanner in = new Scanner(System.in);
  29.  
  30. HashMap<String, ArrayList<int[]>> map = new HashMap<String, ArrayList<int[]>>();
  31.  
  32. int M = in.nextInt();
  33. for(int i=0;i<M;i++)
  34. {
  35. int e = in.nextInt();
  36. int[] corner = new int[e], cost = new int[e];
  37. for(int j=0;j<e;j++)
  38. corner[j] = in.nextInt();
  39. for(int j=0;j<e;j++)
  40. cost[j] = in.nextInt();
  41.  
  42. for(int j=0;j<e;j++)
  43. {
  44. int a = corner[j], b = corner[(j+1)%e], c = cost[j];
  45. String edge = Math.min(a,b)+" "+Math.max(a,b);
  46. if(!map.containsKey(edge))
  47. map.put(edge,new ArrayList<int[]>());
  48. map.get(edge).add(new int[]{i,c});
  49. }
  50. }
  51.  
  52. LinkedList<Edge> edge = new LinkedList<Edge>();
  53. for(ArrayList<int[]> edges : map.values()) {
  54. if(edges.size() == 1)
  55. {
  56. int[] v = edges.get(0);
  57. edge.add(new Edge(v[0], M, v[1]));
  58. }
  59. else
  60. {
  61. int[] v1 = edges.get(0), v2 = edges.get(1);
  62. edge.add(new Edge(v1[0],v2[0],v1[1]));
  63. }
  64. }
  65. parent = new int[map.size()];
  66. Arrays.fill(parent, -1);
  67.  
  68. Collections.sort(edge);
  69. // for (Edge e:edge) {
  70. // System.out.println(e.bv+" "+e.ev+" "+e.cost);
  71. // }
  72. int cnt = 0;
  73. int cost = 0;
  74. boolean work = false;
  75. for(Edge e:edge) {
  76. if(e.ev==M) continue;
  77. int pb = find(e.bv);
  78. int pe = find(e.ev);
  79. if(pb==pe) continue;
  80. union(pb,pe);
  81. cost+=e.cost;
  82. cnt++;
  83. if(cnt==M-1) {
  84. work = true;
  85. break;
  86. }
  87. }
  88. //case 2: including outside
  89. parent = new int[map.size()+1];
  90. Arrays.fill(parent,-1);
  91. int cnt2 = 0;
  92. int cost2 = 0;
  93. for(Edge e:edge) {
  94. int pb = find(e.bv);
  95. int pe = find(e.ev);
  96. if(pb==pe) continue;
  97. //System.out.println(e.bv+" "+e.ev);
  98. union(pb,pe);
  99. cost2+=e.cost;
  100. cnt2++;
  101. if(cnt2==M) {
  102. if(work) System.out.println(Math.min(cost,cost2));
  103. else System.out.println(cost2);
  104. return;
  105. }
  106. }
  107. System.out.println(cost);
  108. }
  109.  
  110. public static int find(int v) {
  111. if (parent[v]==-1) {
  112. return v;
  113. } else {
  114. return parent[v] = find(parent[v]);
  115. }
  116. }
  117.  
  118. public static void union(int pb, int pe) {
  119. parent[pb] = pe;
  120. }
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement