Submission #61170

---

Source Code Expand

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {

	int n, m, K;
	Set<R>[] adj;
	boolean[][] cycle;
	boolean[] u;
	int[] tr;
	
	boolean check(int v, int k, int pre){
		for(int i=0;i<k;i++)if(tr[i]==v){
			for(int j=i;j+1<=k;j++)cycle[tr[j]][tr[j+1]]=cycle[tr[j+1]][tr[j]]=true;
			return true;
		}
		u[v] = true;
		for(R r:adj[v]){
			if(r.t==pre)continue;
			tr[k+1] = r.t;
			if(check(r.t, k+1, v))return true;
		}
		return false;
	}
	
	class R implements Comparable<R>{
		int t, c;
		public R(int t, int c) {
			this.t = t;
			this.c = c;
		}
		@Override
		public int compareTo(R o) {
			return c-o.c;
		}
	}
	
	void dfs(int v){
		if(u[v])return;
		u[v]=true;
		for(R r:adj[v])dfs(r.t);
	}
	
	void run() {
		Scanner sc = new Scanner();
		n = sc.nextInt(); m = sc.nextInt(); K = sc.nextInt();
		cycle = new boolean[n][n];
		adj = new Set[n];
		for(int i=0;i<n;i++)adj[i]=new HashSet<R>();
		int[][] edge = new int[m][3];
		for(int i=0;i<m;i++){
			int s = sc.nextInt()-1, t = sc.nextInt()-1, c = sc.nextInt();
			edge[i][0]=s; edge[i][1]=t; edge[i][2]=c;
			adj[s].add(new R(t, c));
			adj[t].add(new R(s, c));
		}
		u = new boolean[n];
		int cnt = 0;
		for(int i=0;i<n;i++)if(!u[i]){
			cnt++;
			dfs(i);
		}
		if(K <= cnt){
			System.out.println(0); return;
		}
		K-=cnt;
		boolean isCycle = false;
		Arrays.fill(u, false);
		tr = new int[n+5];
		for(int i=0;i<n&&!isCycle;i++)if(!u[i]){
			tr[0] = i;
			u[i] = true;
			isCycle = check(i, 0, -1);
		}
//		System.out.println("K:"+K);
		if(!isCycle){
			List<Integer> l = new ArrayList<Integer>();
			for(int i=0;i<m;i++)l.add(edge[i][2]);
			Collections.sort(l);
			int res = 0;
			for(int i=0;i<K;i++)res+=l.get(i);
			System.out.println(res);
		}
		else{
			int res = 0;
			List<Integer> l = new ArrayList<Integer>();
			for(int i=0;i<m;i++)l.add(edge[i][2]);
			Collections.sort(l);
			for(int i=0;i<=K;i++)res+=l.get(i);
			l.clear();
			for(int i=0;i<m;i++)if(!cycle[edge[i][0]][edge[i][1]])l.add(edge[i][2]);
			Collections.sort(l);
			int r2 = 0;
			if(l.size() < K)r2 = 1<<29;
			else for(int i=0;i<K;i++)r2+=l.get(i);
			System.out.println(Math.min(res, r2));
		}
	}

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		long nextLong() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextLong();
				long res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
		String nextLine(){
			try{
				StringBuilder res =new StringBuilder("");
				int c = System.in.read();
				while (c=='\r' || c=='\n')
					c = System.in.read();
				do {
					res.append((char) c);
					c = System.in.read();
				} while (c!='\r' && c!='\n');
				return res.toString();
			}catch (Exception e) {
				return null;
			}
		}
	}
	
	public static void main(String... args) {
		new Main().run();
	}
}

Submission Info

Compile Error

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result