Submission #2560540
Source Code Expand
import java.util.*; public class Main{ static int n,m; static List<Edge>[] mst; static int[][] vmax; static boolean[] used; public static void main(String[] args){ Scanner sc = new Scanner(System.in); int inf = (int)1e9; n = Integer.parseInt(sc.next()); m = Integer.parseInt(sc.next()); Kruskal kr = new Kruskal(n); for(int i=0; i<m; i++){ int a = Integer.parseInt(sc.next())-1; int b = Integer.parseInt(sc.next())-1; int c = Integer.parseInt(sc.next()); kr.addEdge(a, b, c); } long sum = kr.kruskal(); mst = kr.getMST(); vmax = new int[n][n]; used = new boolean[n]; for(int i=0; i<n; i++){ Arrays.fill(used, false); dfs(i, i); } int q = Integer.parseInt(sc.next()); for(int i=0; i<q; i++){ int s = Integer.parseInt(sc.next())-1; int t = Integer.parseInt(sc.next())-1; System.out.println(sum - vmax[s][t]); } } public static void dfs(int s, int now){ used[now] = true; for(int i=0; i<mst[now].size(); i++){ Edge e = mst[now].get(i); if(!used[e.to]){ int tmp = Math.max(vmax[s][now], e.cost); vmax[s][e.to] = Math.max(vmax[s][e.to], tmp); dfs(s, e.to); } } } } class Kruskal{ private int n; private List<Edge> edge; private List<Edge>[] mst; private UnionFind uf; public Kruskal(int n){ this.n = n; edge = new ArrayList<>(); mst = new List[n]; for(int i=0; i<n; i++){ mst[i] = new ArrayList<>(); } uf = new UnionFind(n); } public void addEdge(int from, int to, int cost){ edge.add(new Edge(from, to, cost)); } public long kruskal(){ long sum = 0; Collections.sort(edge); for(int i=0; i<edge.size(); i++){ Edge e = edge.get(i); if(uf.unite(e.from, e.to)){ mst[e.from].add(new Edge(e.from, e.to, e.cost)); mst[e.to].add(new Edge(e.to, e.from, e.cost)); sum += e.cost; } } return sum; } public List<Edge>[] getMST(){ return mst; } } class UnionFind{ static int[] par; static int[] rank; public UnionFind(int n){ par = new int[n]; Arrays.fill(par, -1); rank = new int[n]; } public static int find(int x){ if(par[x] < 0){ return x; }else{ par[x] = find(par[x]); return par[x]; } } public static boolean unite(int x, int y){ x = find(x); y = find(y); if(x==y) return false; if(rank[x]<rank[y]){ par[x] = y; }else{ par[y] = x; if(rank[x]==rank[y]) rank[x]++; } return true; } public static boolean same(int x, int y){ return find(x)==find(y); } } class Edge implements Comparable<Edge>{ public int from = 0; public int to = 0; public int cost = 0; public Edge(int from, int to, int cost) { this.from = from; this.to = to; this.cost = cost; } @Override public int compareTo(Edge o) { return this.cost - o.cost; } }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | sca1l |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 3710 Byte |
Status | AC |
Exec Time | 2699 ms |
Memory | 244244 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 300 / 300 | 200 / 200 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt |
subtask1 | sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt |
All | sample_1.txt, sample_2.txt, sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | AC | 94 ms | 20820 KB |
sample_2.txt | AC | 95 ms | 19668 KB |
subtask_1_1.txt | AC | 147 ms | 25172 KB |
subtask_1_10.txt | AC | 1768 ms | 134252 KB |
subtask_1_11.txt | AC | 92 ms | 19412 KB |
subtask_1_2.txt | AC | 1293 ms | 119756 KB |
subtask_1_3.txt | AC | 1997 ms | 163112 KB |
subtask_1_4.txt | AC | 983 ms | 123600 KB |
subtask_1_5.txt | AC | 1022 ms | 120812 KB |
subtask_1_6.txt | AC | 1437 ms | 151844 KB |
subtask_1_7.txt | AC | 2023 ms | 165676 KB |
subtask_1_8.txt | AC | 969 ms | 122336 KB |
subtask_1_9.txt | AC | 1126 ms | 116244 KB |
subtask_2_1.txt | AC | 2034 ms | 162092 KB |
subtask_2_2.txt | AC | 2046 ms | 165076 KB |
subtask_2_3.txt | AC | 2026 ms | 166124 KB |
subtask_2_4.txt | AC | 2032 ms | 163332 KB |
subtask_2_5.txt | AC | 1125 ms | 120828 KB |
subtask_2_6.txt | AC | 1227 ms | 101396 KB |
subtask_2_7.txt | AC | 1456 ms | 152712 KB |
subtask_2_8.txt | AC | 2068 ms | 163892 KB |
subtask_3_1.txt | AC | 2677 ms | 243688 KB |
subtask_3_2.txt | AC | 2691 ms | 244076 KB |
subtask_3_3.txt | AC | 1747 ms | 154424 KB |
subtask_3_4.txt | AC | 1834 ms | 154216 KB |
subtask_3_5.txt | AC | 2414 ms | 176164 KB |
subtask_3_6.txt | AC | 2527 ms | 232804 KB |
subtask_3_7.txt | AC | 2699 ms | 240428 KB |
subtask_3_8.txt | AC | 2693 ms | 244244 KB |