[BOJ] 백준 2311. 왕복 여행 (Platinum II)

재밌어보이는 그래프 문제.

문제는 아래와 같다.

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

2311번: 왕복 여행

---

의식의 흐름 및 해설

1->N->1로 돌아가는데, 이미 방문했던 길은 방문할 수 없다.

일단 가중치가 존재하기 때문에 dijkstra나 binary_search를 적절히 이용해볼까 생각이 들었다.

그러나, dijkstra로 1->N까지의 최소 시간은 구한다 치나, N->1로 다시 돌아갈 때, 중복방문을 허용하지 않게 할 방법이 떠오르지 않았다.

 

Kth Shortest Path 알고리즘을 이용해야 하나 싶었지만, 이미 갔던 길을 포함하지 않는 길이 몇 번째 길일지 구하는 것도 쉽지 않아보여서 다른 방법을 고민했다.

 

방법이 잘 생각나지 않아 에라 모르겠다 flow를 보내버리는 overkill을 해버리자고 생각해버렸다. (알고보니 overkill이 아니라 정해였다 ㅎㅎ...)

처음에는 https://www.acmicpc.net/problem/2316 (도시 왕복하기 2) 처럼 도시를 두 개로 나눠서 처리할까 했다. 이렇게 해결하는 방법도 가능할 듯하다.

그런데, 그냥 Source->1 용량과 N->Sink용량을 2로 설정해주고, 나머지 용량은 1로 설정해버리면 mcmf를 이용해 1->N->1이나, 1->N을 두 번 이용하되, 중복방문을 제외하기 위해 각 길의 용량을 1로 하는 방법이나, 똑같기 때문에 이렇게 해서 해결하였다.

 

 

아, 그리고 MCMF코드를 dinic 형태에 맞춰서 바꿔볼까 하다가,

mcmf는 spfa + dfs 형태도 아직 많이 쓰는 것 같아 mcmf는 이전 형태 코드를 그대로 유지하며 사용중이다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int MAX = 1003;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e6;
int N, M, w, ans;
struct Edge {
	int to, c, f, cost;
	Edge* rev;
	Edge() :Edge(-1, 0, 0) {}
	Edge(int to1, int c1, int cost1)
		:to(to1), c(c1), f(0), cost(cost1), rev(nullptr) {}
	int remain() {
		return c - f;
	}
	void push(int x) {
		f += x;
		rev->f -= x;
	}
};
vector<Edge*> v[MAX];
inline void addEdge(int a, int b, int c, int cost) {
	Edge* e1 = new Edge(b, c, cost);
	Edge* e2 = new Edge(a, 0, -cost);
	e1->rev = e2;
	e2->rev = e1;
	v[a].push_back(e1);
	v[b].push_back(e2);
}
void mcmf(int s, int e) {
	while (1) {
		int prev[MAX], d[MAX];
		Edge* path[MAX];
		bool inQ[MAX];
		fill(prev, prev + MAX, -1);
		fill(d, d + MAX, INF);
		fill(path, path + MAX, nullptr);
		fill(inQ, inQ + MAX, false);
		queue<int> q;
		q.push(s);
		d[s] = 0;
		inQ[s] = true;
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			inQ[x] = false;
			for (Edge* i : v[x]) {
				int next = i->to;
				if (i->remain() > 0 && d[next] > d[x] + i->cost) {
					prev[next] = x;
					path[next] = i;
					d[next] = d[x] + i->cost;
					if (!inQ[next]) {
						q.push(next);
						inQ[next] = true;
					}
				}
			}
		}
		if (prev[e] == -1)
			break;
		int flow = INF;
		for (int i = e; i != s; i = prev[i]) {
			flow = min(flow, path[i]->remain());
		}
		for (int i = e; i != s; i = prev[i]) {
			path[i]->push(flow);
			w += path[i]->cost;
		}
		ans += flow;
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;
	int S = 0, E = 1001;
	addEdge(S, 1, 2, 0);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		addEdge(a, b, 1, c);
		addEdge(b, a, 1, c);
	}
	addEdge(N, E, 2, 0);
	mcmf(S, E);
	cout << w << "\n";
}

---

오랜만에 풀어본 MCMF 문제.

사실 거의 몇달만에 풀어본 것 같다.

MCMF, flow 문제들은 거의 풀어보지 않아서 그런지, 이 문제가 요구하는 알고리즘이 맞는지 확신이 안 설 때가 많은데, 많이 접해보도록 해야겠다.