BOJ 3640 - 제독

링크: https://www.acmicpc.net/problem/3640

문제

가중치가 있는 방향 그래프가 주어지고, 1번 정점에서 V번 정점까지 서로 겹치지 않는 2개의 경로 중 비용이 최소인 경우를 출력하는 문제이다.

겹치지 않는 경로를 찾는 것은 최대 유량으로 해결 가능하고, 그 비용이 최소가 되는 것을 구해야하므로, 네트워크 플로우 유형 중에서 MCMF(Min Cost Max Flow; 최소 비용 최대 유량)인 문제이다.

그래프 문제는 항상 문제 조건을 꼼꼼히 살펴야겠다.

이번에도 "출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지나면 안 된다." 에서 정점이 겹쳐서는 안되는 조건을 깜빡해서 계속 틀렸다.

이 조건을 무시하면 틀리는 예외 케이스는 아래와 같다.

최대 유량은 1개이고, 답은 4.

5 6
1 2 5
1 3 2
2 3 3
3 4 4
3 5 2
4 5 3

정점이 겹치면 안되므로, 정점을 분할하여 해결하면 된다.

코드

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long lld;
	typedef pair<int, int> ii;
	const int INF = 0x3f3f3f3f;
	const lld LNF = 0x3f3f3f3f3f3f3f3f;
	const int MOD = 1e9 + 7;
	struct edge {
	int next, flow, cap, d;
	edge* rev;
	edge(int next, int cap, int d = 0) : next(next), flow(0), cap(cap), rev(0), d(d) {}
	void add(int f) {
	flow += f;
	rev->flow -= f;
	}
	int sparse() {
	return cap - flow;
	}
	};
	#define MAX_V 2050
	vector<edge*> adj[MAX_V];
	// (cost, flow)
	pair<lld, int> mcmf(int src, int sink) {
	lld cost = 0;
	int mf = 0;
	int prv[MAX_V];
	edge* pth[MAX_V];
	bool inQ[MAX_V];
	int dist[MAX_V];
	while (true) {
	memset(prv, -1, sizeof(prv));
	memset(pth, 0, sizeof(pth));
	memset(inQ, 0, sizeof(inQ));
	memset(dist, 0x3f, sizeof(dist));
	queue<int> q;
	q.push(src);
	dist[src] = 0;
	// spfa
	while (!q.empty()) {
	int cur = q.front();
	q.pop();
	inQ[cur] = false;
	for (auto& e : adj[cur]) {
	int nxt = e->next;
	if (e->sparse() > 0 && dist[nxt] > dist[cur] + e->d) {
	dist[nxt] = dist[cur] + e->d;
	prv[nxt] = cur;
	pth[nxt] = e;
	if (inQ[nxt]) continue;
	q.push(nxt);
	inQ[nxt] = true;
	}
	}
	}
	if (prv[sink] == -1) break;
	int flow = INF;
	for (int i = sink; i != src; i = prv[i])
	flow = min(flow, pth[i]->sparse());
	for (int i = sink; i != src; i = prv[i]) {
	cost += (lld)flow * pth[i]->d;
	pth[i]->add(flow);
	}
	mf += flow;
	}
	return { cost, mf };
	}
	void add_flow(int u, int v, int cap, int dist) {
	edge* p = new edge(v, cap, dist);
	edge* q = new edge(u, 0, -dist);
	p->rev = q;
	q->rev = p;
	adj[u].push_back(p);
	adj[v].push_back(q);
	}
	const int src = MAX_V - 1, sink = MAX_V - 2;
	int main() {
	int v, e;
	while (~scanf("%d %d", &v, &e)) {
	adj[src].clear();
	adj[sink].clear();
	for (int i = 1; i <= 2 * v; ++i) adj[i].clear();
	add_flow(src, 1, 2, 0);
	add_flow(v + v, sink, 2, 0);
	for (int i = 1; i <= v; ++i) {
	int cap = i == 1 || i == v ? 2 : 1;
	add_flow(i, i + v, cap, 0);
	}
	while (e--) {
	int a, b, w;
	scanf("%d %d %d", &a, &b, &w);
	add_flow(a + v, b, 1, w);
	}
	auto ans = mcmf(src, sink);
	printf("%lld\n", ans.first);
	}
	return 0;
	}

view raw boj-3640.cpp hosted with ❤ by GitHub