codeforces #597 div2 D - Shichikuji and Power Grid ( MST )

https://codeforces.com/contest/1245/problem/D

 

도시(최대 2000)마다 좌표, 파워설치비용, 간선연결가중치가 주어진다.

 

0번도시를 dummy vertex로 두고, 이 도시랑 연결하는 비용을 파워 설치 비용으로 둔 후, 모든 간선을 정렬하여 mst를 수행한다. mst를 뽑을 때 한 쪽 정점이 0번도시라면 그 도시는 파워를 설치한 도시이고, 양쪽 다 0번이 아니라면 두 도시는 연결된 도시이다.

 

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int MAX = 2001;

struct Edge {
	int u, v;
	ll w;
	Edge(int u1,int v1, ll w1):u(u1),v(v1),w(w1){}
	bool operator <(Edge e) {
		return this->w < e.w;
	}
};

ll dist(int x1, int y1, int x2, int y2) {
	return abs(x1 - x2) + abs(y1 - y2);
}

int uf[MAX];
int find(int a) {
	if (uf[a] == -1) return a;
	return uf[a] = find(uf[a]);
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	uf[a] = b;
	return true;
}

int main() {
	int n; cin >> n;
	ll x[MAX], y[MAX], c[MAX], k[MAX];

	for (int i = 1; i <= n; i++)
		cin >> x[i] >> y[i];	
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	for (int i = 1; i <= n; i++)
		cin >> k[i];

	vector<Edge> e;
	for (int i = 1; i <= n; i++) {
		e.push_back(Edge(i, 0, c[i]));
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			e.push_back(Edge(i, j, (k[i] + k[j]) * dist(x[i], y[i], x[j], y[j])));
		}
	}
	sort(e.begin(), e.end());

	ll ans = 0;
	vector<int> power_plants;
	vector<P> connections;

	fill(uf, uf + MAX, -1);
	int cnt = 0;
	for (int i = 0;; i++) {
		if (merge(e[i].u, e[i].v)) {
			ans += e[i].w;
			if (e[i].v == 0)
				power_plants.push_back(e[i].u);
			else
				connections.push_back({ e[i].u,e[i].v });
			
			if (++cnt == n) break;
		}
	}

	cout << ans << '\n' <<power_plants.size() << '\n';
	for (int ctt : power_plants)
		cout << ctt << " ";
	cout << '\n' << connections.size() << '\n';
	for (P ctt : connections)
		cout << ctt.first << " " << ctt.second << '\n';
}

 

 

생각)

u,v사이에 간선을 만들 때 v의 파워설치 비용보다 간선설치비용이 싼 경우만 간선으로 해서 그 간선들을 정렬한 후, mst를 수행하는 논리로 풀어봤지만, 논리가 약해서 13번 테케를 통과하지 못했다. 아예 invalid한 논리였던 것 같다. 위의 풀이는 editorial을 참고했다. editorial에선 prim's algorithm을 사용했지만 크루스칼로 풀어봤다.

 

+)

그래프 문제 중 되게 어려워 보이는 문제도 이렇게 더미정점을 추가해서 푸는 문제가 종종 있는 것 같다. 문제풀때마다 유념해야겠다.