최소 스패닝 트리 보다 다음 으로 작은 스패닝 트리를 찾는 문제이다.
MST를 구해주고 MST를 구성하지 않는 간선을 가지고 계산한다.
그 간선의 정보가 {$d$, $u$,$v$}일때 $u$,$v$ 정점의 LCA까지 최대 간선길이를 구한다.
(LCA에서 par저장하듯이 최대 간선길이도 저장하면 됨)
예외가 있는데 만약 그 간선길이가 $d$와 같다면 두 번째 스패닝 트리가 없는걸로 판단할 수 있기 때문에
LCA에서 depth를 2배씩 늘려가며 올라가듯 $d$보다 작지만 가장 큰 간선을 찾으면 된다.
참고로 merge연산할 때 find()이후의 정점을 가지고 다른 정보를 저장하면 당연히 안된다.
(개뻘짓함..)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, pair<int, int>> P;
#define mp(a,b) make_pair(a,b)
#define mt(a,b,c) mp(a,mp(b,c))
struct Edge {
int d, u, v;
Edge() : Edge(-1, -1, 0) {}
Edge(int dd, int uu, int vv) : u(uu), v(vv), d(dd) {}
bool operator <(const Edge& O)const { return d < O.d; }
};
int N, M;
Edge adj[200001];
bool isMST[200001];
int group[50001], trank[50001];
vector<pair<int, int>> MST[50001];
int depth[50001], par[50001][21], cost[50001][21];
void init() {
for (int n = 1;n <= N;n++) {
group[n] = n;
depth[n] = -1;
for (int m = 0;m < 21;m++)
par[n][m] = -1;
}
for (int m = 0;m < M;m++)
isMST[m] = false;
}
int find(int x) {
if (x == group[x]) return x;
return group[x] = find(group[x]);
}
void merge(int a, int b) {
if (trank[a] > trank[b]) swap(a, b);
else if (trank[a] == trank[b]) trank[b]++;
group[a] = b;
}
void dfs(int here) {
for (auto n : MST[here]) {
int next = n.second;
if (depth[next] == -1) {
depth[next] = depth[here] + 1;
par[next][0] = here;
cost[next][0] = n.first;
dfs(next);
}
}
}
int second_max(int u, int i, int d) {
if (i == 0) return 0;
int ret = 0;
if (cost[u][i - 1] == d)
ret = max(ret, second_max(u, i - 1, d));
else ret = max(ret, cost[u][i - 1]);
if (cost[par[u][i - 1]][i - 1] == d)
ret = max(ret, second_max(par[u][i - 1], i - 1, d));
else ret = max(ret, cost[par[u][i - 1]][i - 1]);
return ret;
}
int LCA_max(int u, int v, int d) {
if (depth[u] > depth[v]) swap(u, v);
int dmax = 0;
if (depth[u] != depth[v]) {
for (int i = 20;i >= 0;i--) {
if (depth[v] - depth[u] >= (1 << i)) {
if (cost[v][i] == d) dmax = max(dmax, second_max(v, i, d));
else dmax = max(dmax, cost[v][i]);
v = par[v][i];
}
}
}
if (u == v) return dmax;
for (int i = 20;i >= 0;i--) {
if (par[u][i] != -1 && par[u][i] != par[v][i]) {
if (cost[v][i] == d) dmax = max(dmax, second_max(v, i, d));
else dmax = max(dmax, cost[v][i]);
if (cost[u][i] == d) dmax = max(dmax, second_max(u, i, d));
else dmax = max(dmax, cost[u][i]);
u = par[u][i];
v = par[v][i];
}
}
if (cost[u][0] < d) dmax = max(dmax, cost[u][0]);
if (cost[v][0] < d) dmax = max(dmax, cost[v][0]);
return dmax;
}
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] = Edge(d, u, v);
}
sort(adj, adj + M);
bool flag = false;
int mst1 = 0, cnt = 0;
for (int m = 0;m < M;m++) {
int d = adj[m].d,
u = adj[m].u,
v = adj[m].v;
u = find(u), v = find(v);
if (u == v) continue;
if (u != v){ //MST 간선 가능
merge(u, v);
isMST[m] = true;
//find이후의 u,v를 넣으면 안된다!!!! (u,v)가 변경되있는 상태
MST[adj[m].u].push_back({ d,adj[m].v });
MST[adj[m].v].push_back({ d,adj[m].u });
cnt++;
mst1 += d;
}
if (cnt == N - 1) {
flag = true;
break;
}
}
if (!flag) { //MST가 없을 때
printf("-1\n");
return 0;
}
depth[1] = 0;
par[1][0] = 0;
cost[1][0] = 0;
dfs(1);
//부모노드, 간선길이 전처리
for (int m = 1;m < 21;m++) {
for (int n = 1;n <= N;n++) {
par[n][m] = par[par[n][m - 1]][m - 1];
cost[n][m] = max(cost[par[n][m - 1]][m - 1], cost[n][m - 1]);
}
}
long long ans = (long long )3e13;
for (int m = 0;m < M;m++) {
if (isMST[m]) continue;
//MST간선이 아닌것들에서 골라준다.
int d = adj[m].d,
u = adj[m].u,
v = adj[m].v;
int get_MAX_d = LCA_max(u, v, d); //d보단 작지만 가장 큰 간선
ans = min(ans, (long long)(mst1 + d - get_MAX_d)); //d를 넣고 MST중 가장 큰 간선을 뺀다.
}
if (ans == mst1 || ans == (long long)3e13)printf("-1\n");
else printf("%lld\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기