글 읽기 - MST 질문입니다.

lyzqm 6년 전 0

이 문제를 풀려고 하는데요.

해당 간선을 사용하지 않고 MST를 구하는 문제입니다.

만약 다음과 같은 그래프가 있다고 합시다.

붉은색선은 MST의 트리간선이고 초록색은 트리간선이 아닌 간선입니다.

파란x 표시되있는 간선을 지우고 나머지 MST는 유지한채 트리간선이 아닌 다른간선(초록선)으로 대체하려고 하는데요.

(물론 초록선중에 값이 작은놈으로 대체)

이것이 해당 조건에 맞는 MST를 구하는 방법이 맞는지 모르겠네요...

반례가 있을까요? 도와주세요

smu201111192 6년 전 0

네 올바른 방법 같습니다.

1. 스패닝트리 엣지가 아닌 다른엣지를 지운다면, 원래 만든 mst가 답이 될거고,

2. 스패닝트리 엣지를 지운다면 해당 엣지를 기준으로 분리된 subtree가 2개가 생깁니다.

이 경우 분리된 두 subtree를 연결할수 있는 최소의 엣지를 찾으면됩니다.

lyzqm 6년 전 0

감사합니다.

사실 고민하는도중 풀이가 맞다는것을 깨달았는데요.

또 다른 문제는 답변해주신 2번방법인데 문제에서 query가 M번들어오니 적어도 하나의 query에 O(logM)으로 해결해야할 것 같은데

마땅한 전처리 방법이 생각나지 않네요..

혹시 아신다면 힌트 주시면 감사하겠습니다 ㅋㅋ..

smu201111192 6년 전 0

1.mst를 구축합니다.

2.mst에 속하지 않은 엣지를 오름차순으로 정렬해서 저장합니다.

3.mst에 속하지 않은 엣지를 작은거부터 꺼냅니다.

현재보고 있는 엣지 i (mst 에 속하지 않은)가 버텍스 u,v를 연결하고 있고 그때의 가중치는 w라고 해봅시다.

i를 mst에 추가하면 path (u,v)상에 있는 어떤 엣지를 끊어도 트리는 유지가됩니다.

이 점을 이용해서 오프라인으로 푸시면 될거 같네요.

lyzqm 6년 전 0

답변 감사합니다.

참고해서 풀어볼게요!

smu201111192 6년 전 0

path(u,v)상의 엣지는 i보다 뒤의 엣지로도 대체 가능할 수도 있겟지만,

이 경우 항상 손해를 봅니다. (w[i] <= w[i+1])

그러므로 대체 가능한 엣지를 찾은 엣지들은 더 이상 고려하지 않도록 해주시면 될거같네요.

lyzqm 6년 전 0

@smu201111192

9%정도에서 시간초과가 나는데 제 풀이 봐주실 수 있나요?

말씀하신대로 mst가 아닌 간선들을 오름차순으로 정렬한다음에 작은것 부터 꺼냈는데요.

해당 간선이 {u,v}이면 path(u,v)로 대체할 수 있기 때문에 그 경로를 찾기위해서 위와 같이 {u,v}의 MST LCA를 구했습니다.

그러면 ① 번 과정인 path(u, lca)를 탐색하며 아직 대체하지 못하는 경로인경우 갱신해줍니다.

②번 과정도 마찬가지로 path(v, lca)를 탐색하며 갱신해줍니다.

탐색할때는 u나 v에서 depth를 한칸씩 내리면서 탐색하는데요. 이 작업이 많아서 TLE가 나오는것 같습니다.

시간을 좀 줄일 수 있는 방법이 있을까요?

코드도 같이 올릴게요.

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int N, M;
int par[100001], rrank[100001], depth[100001];
int edge[200001];
ll ans[200001];
int pprev[100001][21];
bool isMSTedge[200001];
pair<ll, pair<int, pair<int, int>>> adj[200001];	//(d, index, u, v)
ll adj_copy[200001];
vector<pair<ll, pair<int, int>>> adj_mst[100001];		//u - (d, index, v)
pair<ll, pair<int,int>> adj_n_mst[200001];		//MST아닌 간선 (d, u, v)
void init() {
	memset(depth, -1, sizeof depth);
	for (int n = 0;n < M;n++) ans[n] = -1;
	for (int n = 1;n <= N;n++) 
		par[n] = n, rrank[n] = 0;
}
int find(int x) {
	if (x == par[x]) return x;
	return par[x] = find(par[x]);
}
bool merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return false;
	if (rrank[u] > rrank[v]) swap(u, v);
	else if (rrank[u] == rrank[v]) rrank[v]++;
	par[u] = v;
	return true;
}
void dfs(int here) {
	for (auto n : adj_mst[here]) {
		int next = n.second.second;
		if (depth[next] == -1) {
			int idx = n.second.first;
			depth[next] = depth[here] + 1;
			pprev[next][0] = here;
			edge[next] = idx;
			dfs(next);
		}
	}
}
void preprocess() {
	for (int j = 1;j < 21;j++) {
		for (int i = 1;i <= N;i++) {
			pprev[i][j] = pprev[pprev[i][j - 1]][j - 1];
		}
	}
}
int getLCA(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);
	for (int i = 20;i >= 0;i--) {
		if (depth[u] - depth[v] >= (1 << i))
			u = pprev[u][i];
	}
	if (u == v) return u;
	for (int i = 20;i >= 0;i--) {
		if (pprev[u][i] != pprev[v][i])
			u = pprev[u][i], v = pprev[v][i];
	}
	return pprev[u][0];
}
int main() {
	scanf("%d%d", &N, &M);
	init();
	for (int m = 0;m < M;m++) {
		int u, v, d;
		scanf("%d%d%d", &u, &v, &d);
		adj[m] = { (ll)d,{m,{u,v} } };
		adj_copy[m] = (ll)d;
	}

	sort(adj, adj + M);
	ll mst_val = 0;
	int mst_cnt = 0;	//
	int n_mst_cnt = 0;
	for (int m = 0;m < M;m++) {
		ll d = adj[m].first;
		int u = adj[m].second.second.first, v = adj[m].second.second.second;
		if (merge(u, v) && mst_cnt < N - 1) {		//서로다른 집합인 경우 - MST
			int idx = adj[m].second.first;
			isMSTedge[idx] = true;
			adj_mst[u].push_back({ d, { idx, v } });
			adj_mst[v].push_back({ d, { idx, u } });
			mst_val += d;
			++mst_cnt;
		}
		else {		//MST아닌 간선
			adj_n_mst[n_mst_cnt] = { d,{u,v} }, ++n_mst_cnt;
		}
	}
	if (mst_cnt != N - 1) {
		for (int m = 0;m < M;m++) printf("-1\n");
		return 0;
	}

	depth[1] = 0;
	dfs(1);
	preprocess();		//2^K의 자식노드 전처리

	int cnt = 0;
	sort(adj_n_mst, adj_n_mst + n_mst_cnt);
	for (int m = 0;m < n_mst_cnt;m++) {
		ll d = adj_n_mst[m].first;
		int u = adj_n_mst[m].second.first, v = adj_n_mst[m].second.second;

		int lca = getLCA(u, v);

		while (lca != u) {		// path(u, lca)
			int idx = edge[u];
			if (ans[idx] == -1) {
				cnt++;
				ans[idx] = mst_val + d - adj_copy[idx];
			}
			u = pprev[u][0];
		}
		while (lca != v) {		// path(v, lca)
			int idx = edge[v];
			if (ans[idx] == -1) {
				cnt++;
				ans[idx] = mst_val + d - adj_copy[idx];
			}
			v = pprev[v][0];
		}
		if (cnt == mst_cnt) break;
	}
	for (int m = 0;m < M;m++) {
		if (!isMSTedge[m]) printf("%lld\n", mst_val);		//mst가 아닌 간선 - 변함없음
		else printf("%lld\n", ans[m]);
	}
	return 0;
}

lyzqm 6년 전 0

으아 아닙니다

해결했네요 ㅠ_ㅠ!

smu201111192 6년 전 1

이제 봤네요 ~ 축하드립니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

MST 질문입니다.

lyzqm 6년 전 0

smu201111192 6년 전 0

lyzqm 6년 전 0

smu201111192 6년 전 0

lyzqm 6년 전 0

smu201111192 6년 전 0

lyzqm 6년 전 0

lyzqm 6년 전 0

smu201111192 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말