취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 4352번 문제인 Jogging Trails이다.
문제는 아래 링크를 확인하자.

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

주어지는 그래프에 기존에 있던 에지만을 다시 추가해 오일러회로가 존재하는 최소 가중치의 그래프를 만드는 문제이다.

오일러 회로가 존재할 필요충분조건은 해당 그래프가 연결그래프이며 동시에 모든 정점의 degree가 짝수인 것과 같다는 것이다. 문제에서 주어진 그래프가 연결그래프임은 보장되어 있으므로, 모든 정점의 degree를 짝수로 만들어주어야 한다.

degree가 홀수인 정점의 degree를 짝수로 바꾸기 위해, degree가 짝수인 정점에도 또한 에지가 추가되는 경우가 존재한다는 점을 잊지 말자. 예를 들어 degree가 홀수인 두 노드 1과 3 을 잇는 에지의 거리가 100이지만 degree가 짝수인 노드 2에 대하여 1과 2, 2와 3을 잇는 에지의 거리가 각각 20이라면 1과 2, 2와 3을 잇는 두 에지를 긋는 것이 1과 3을 잇는 에지를 긋는 것보다 이득일 것이다.

대신, 두 degree가 홀수인 노드를 짝수인 노드로 치환하기 위해 두 노드 사이의 최단경로를 따라 모든 에지를 하나씩 추가하는 전략을 이용할 수 있다. 모든 두 노드 사이의 거리를 floyd-warshall 알고리즘을 이용해 전처리한 후 이 거리정보를 이용하여 편하게 구현하자.

이제, degree가 홀수인 정점들끼지 짝을 짓는 가능한 모든 경우의 수를 전부 시도해 그들 사이를 최단거리로 잇는 경로에 해당하는 에지를 전부 추가해 추가되는 에지의 거리의 최솟값을 구하는 것으로 문제를 해결하자.

모든 에지의 거리만큼은 최소한 다 걸어야하므로 이 값을 답에 추가하는 것을 잊지 말자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

int N, M;
int indegree[16];
ll dist[16][16];
ll ans;

ll tmp = 0;
void func(int idx) {
	if (idx > N) {
		ans = min(ans, tmp);
		return;
	}
	if (indegree[idx] == 0) func(idx + 1);
	else {
		for (int i = idx + 1; i <= N; i++) {
			if (indegree[i] == 1) {
				indegree[i] = 0;
				tmp += dist[idx][i];
				func(idx + 1);
				tmp -= dist[idx][i];
				indegree[i] = 1;
			}
		}
	}
}

void solve() {
	ll ans_base = 0;
	memset(indegree, 0, sizeof(indegree));
	for (int i = 1; i <= N; i++) {
		dist[i][i] = 0;
		for (int j = i + 1; j <= N; j++) dist[i][j] = dist[j][i] = 1000000007;
	}

	while (M--) {
		int x, y; ll d; cin >> x >> y >> d;
		ans_base += d;
		dist[x][y] = dist[y][x] = min(dist[x][y], d);
		indegree[x] ^= 1;
		indegree[y] ^= 1;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	ans = 1000000007;
	func(1);

	cout << ans_base + ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	while (cin >> N >> M) {
		solve();
	}
}