[백준] 21924. 도시건설 (java)

https://www.acmicpc.net/problem/21924

21924번: 도시 건설

 

문제

채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.

공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다.

채완이는 공사하는 데 드는 비용을 아끼려고 한다. 

모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다.

위 그림에서 건물과 직선으로 표시된 도로, 해당 도로를 만들 때 드는 비용을 표시해놓은 지도이다.

그림에 있는 도로를 다 설치할 때 드는 비용은 62이다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35이다.

채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있다.

채완이를 대신해 얼마나 절약이 되는지 계산해주자.

출력

예산을 얼마나 절약 할 수 있는지 출력한다. 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.

 

풀이

너무나 전형적인 MST 최소스패닝트리 문제

그런데 범위가 지랄맞게도 int형을 넘어서기 때문에 (정말 문제좀 잘 읽어야 할 듯. 심각)

long으로만 잘 해주면,, 10분컷 가능한 문제

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


// 12:33-12:45
public class boj_21924_도시건설 {
	static int N,M;
	static ArrayList<Node>[] list;
	static class Node implements Comparable<Node>{
		int to;
		int weight;
		Node(int to,int weight){
			this.to = to;
			this.weight = weight;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}

		@Override
		public String toString() {
			return "Node [to=" + to + ", weight=" + weight + "]";
		}
		
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[N+1];
		for(int i=1; i<N+1; i++)
			list[i] = new ArrayList<>();
		
		long total = 0;
		int a,b,w;
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			
			list[a].add(new Node(b,w));
			list[b].add(new Node(a,w));
			total += w;
		}
		
		long cost = go();
		System.out.println(cost==-1 ? -1 : total-cost);
		
	}
	
	public static long go() {
		long sum = 0;
		int cnt = 0;
		boolean[] visited = new boolean[N+1];
		PriorityQueue<Node> queue = new PriorityQueue<>();
		queue.offer(new Node(1,0));
		
		while(!queue.isEmpty()) {
			if(cnt==N) break;
			Node now = queue.poll();
			
			if(visited[now.to]) continue;
			visited[now.to] = true;
			sum += now.weight;
			cnt++;
			
			for(Node next : list[now.to]) {
				if(visited[next.to]) continue;
				
				queue.offer(next);
			}
		}
		
		
		return cnt==N ? sum : -1;
	}

}