Advertisement
Guest User

Untitled

a guest
Jan 25th, 2020
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.91 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3. //https://pastebin.com/4GZTgn5h
  4. public class ccc17s4 {
  5. public static int[] parent;
  6. public static class Edge implements Comparable<Edge> {
  7. int bv;
  8. int ev;
  9. int cost;
  10. int active; //0 represent active 1 represent inactive
  11. public Edge(int bv, int ev, int cost, int active) {
  12. this.bv = bv;
  13. this.ev = ev;
  14. this.cost = cost;
  15. this.active = active;
  16. }
  17. @Override
  18. public int compareTo(Edge o) {
  19. if (this.cost>o.cost) {
  20. return 1;
  21. } else if (this.cost<o.cost) {
  22. return -1;
  23. } else {
  24. if (this.active<o.active) {
  25. return -1;
  26. } else if (this.active>o.active) {
  27. return 1;
  28. } else {
  29. return 0;
  30. }
  31. }
  32. }
  33. }
  34. public static void main(String[] args) {
  35. // TODO Auto-generated method stub
  36. // 5 6 2 N is vertice amount M is Edge amount D enhancer
  37. // 1 2 5
  38. // 2 3 5
  39. // 1 4 5
  40. // 4 5 5
  41. // 1 3 1
  42. // 1 5 1
  43.  
  44. Scanner sc = new Scanner(System.in);
  45. int N = sc.nextInt(); //V
  46. int M = sc.nextInt(); //E
  47. int D = sc.nextInt(); //enhancer
  48. Edge[] edges = new Edge[M];
  49. //input M edges
  50. for (int i=0; i<M; i++) {
  51. int bv = sc.nextInt()-1;
  52. int ev = sc.nextInt()-1;
  53. int cost = sc.nextInt();
  54. int active = 1;
  55. if (i<N-1) {
  56. active = 0;
  57. }
  58. edges[i] = new Edge(bv,ev,cost,active);
  59. }
  60. Arrays.sort(edges);
  61. //sort the edge array
  62.  
  63. parent = new int[N];
  64. Arrays.fill(parent, -1);
  65.  
  66. int day = 0;
  67. int lastActive = 0; //check the last pipe active mode
  68. int lastCost = 0;
  69. int index = 0;
  70. //Read edge one by one from edges array
  71. for (int i=0; i<M; i++) {
  72. int pb = find(edges[i].bv);
  73. int pe = find(edges[i].ev);
  74. if (pb!=pe) {
  75. //Add into tree
  76. union(pb,pe);
  77. day += edges[i].active; //how many inactive pipe
  78. index++;
  79. if (index==N-1) {
  80. lastActive = edges[i].active;
  81. lastCost = edges[i].cost;
  82. break;
  83. }
  84. }
  85. }
  86. if (lastActive==1) {
  87. Arrays.fill(parent, -1);
  88. for (int i=0; i<M; i++) {
  89. int pb = find(edges[i].bv);
  90. int pe = find(edges[i].ev);
  91. if (pb!=pe) {
  92. //Add into tree
  93. if (edges[i].cost<lastCost || (edges[i].cost==lastCost && edges[i].active==0)) {
  94. union(pb,pe);
  95. index++;
  96. } else if (edges[i].cost>lastCost && edges[i].active==0 && edges[i].cost<=D){
  97. //replace this one with last one
  98. day--;
  99. break;
  100. }
  101. }
  102. }
  103. }
  104. System.out.println(day);
  105. //if lastActive equals to inactive
  106. //we can enhance an edge which using enhancer to
  107. //reduce to cost to 0 to replace the last pipe
  108.  
  109. //1 2 3 4 5 10 6
  110.  
  111. //1 2 3 4 6 10
  112.  
  113. //1 3 6 9 11
  114. }
  115.  
  116. public static int find(int v) {
  117. if (parent[v]==-1) {
  118. return v;
  119. } else {
  120. return parent[v] = find(parent[v]);
  121. }
  122. }
  123. public static void union(int pb, int pe) {
  124. parent[pb] = pe;
  125. }
  126.  
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement