BOJ 18857 집 떠나와 열차 타고

문제 링크입니다.

문제 요약

무방향 가중치 간선 선인장의 최소 $s$-$t$ 컷을 구하세요.

풀이

주어진 그래프를 사이클에 대한 트리로 해석합니다. 1번 정점에서 $V$번 정점까지 이동하는 단순 경로 중 지나는 사이클의 집합은 유일하게 결정되므로, DFS를 한 번 돌려 경로를 아무거나 하나 찾고 필요한 정점만 남기면 사이클을 0개 이상의 간선으로 이어붙인 사슬 모양을 얻을 수 있습니다.

이 사슬을 최소 비용으로 끊어야 합니다. 두 가지 경우가 있는데, 사이클을 끊는 경우와 두 사이클을 잇는 중간 간선을 끊는 경우입니다. 중간 간선은 그냥 끊으면 되고, 사이클은 위쪽 경로와 아래쪽 경로에서 간선을 하나씩 끊어줘야 합니다.

마찬가지로 DFS를 통해 사이클을 찾습니다. DFS 상에서 방문한 간선을 적당히 스택에 저장했다가 되짚는 방식으로 사이클 위의 모든 정점을 찾을 수 있고, 이때 사이클 위의 각 정점 별로 사이클에 진입한 정점을 기준으로 왼쪽으로 돌아 해당 정점까지 이동했을 때 지나는 간선의 최소 가중치와, 오른쪽으로 돌았을 때 지나는 최소 가중치를 모두 구할 수 있습니다. 만약 방문한 뒤 스택에 최근 간선이 사이클로 처리되지 않고 남아 있다면 두 사이클을 잇는 경우이므로 답에 바로 갱신해 줄 수 있습니다.

사이클을 감지한 뒤 해당 사이클에 다시 방문하지 못하도록 적절한 방문 처리를 해주면 ${\cal O} (V+E)$에 문제를 해결할 수 있습니다. 제 코드는 방문 처리에 std::map을 써서 로그가 하나 붙었습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1234567890;
vector<pii> e[424242];
int n, m, l[424242], r[424242];
set<int> dead[424242]; stack<pii> stk;
bool vis[424242], on_path[424242];
int ans = INF;

bool get_path(int now){
	vis[now] = 1;
	if(now == n){on_path[now] = 1; return 1;}
	for(auto& [nxt, w] : e[now]) if(!vis[nxt]) if(get_path(nxt)){on_path[now] = 1; return 1;}
	return 0;
}

void dfs(int now, int pre){
	if(vis[now]){
		l[now] = r[now] = INF;
		stack<pii> rev;
		int last = now;
		int idx = 0;
		do{
			auto [nxt, w] = stk.top(); stk.pop();
			rev.push({last, w});
			if(idx == 0 && on_path[nxt]) idx = nxt;
			l[nxt] = min(l[last], w);
			last = nxt;
		} while(last != now);
		do{
			auto [nxt, w] = rev.top(); rev.pop();
			r[nxt] = min(r[last], w);
			last = nxt;
		} while(last != now);
		assert(rev.empty());
		if(idx != 0 && idx != now) ans = min(ans, l[idx]+r[idx]);
		dead[now].insert(pre);
		return;
	}
	vis[now] = 1;
	for(auto& [nxt, w] : e[now]) if(nxt != pre && !dead[now].count(nxt)){
		stk.push({now, w}); dfs(nxt, now);
		if(!stk.empty() && stk.top() == make_pair(now, w)){
			if(on_path[nxt]) ans = min(ans, w);
			stk.pop();
		}
	}
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	cin >> n >> m;
	while(m--){
		int u, v, w; cin >> u >> v >> w;
		e[u].push_back({v,w}); e[v].push_back({u, w});
	}
	get_path(1);
	memset(vis, 0, sizeof(vis)); dfs(1, 0); cout << ans;
}