코뚫린 앙드로이드

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

이 문제를 해결하는데 많은 시간이 걸렸고, 질문 게시판에서 힌트를 얻은 뒤에 풀 수 있었습니다.

왜 오래걸렸고, 유의해야될 점이나, 어떤식으로 풀어야되는지 포스팅 해보도록 하겠습니다.

아마 이문제를 풀기전에 https://www.acmicpc.net/problem/11657(타임머신), https://www.acmicpc.net/problem/1865(웜홀) 문제를 푸셨을텐데 단지, 코드를 외워서 풀었다면 저처럼 이문제에서 많은 어려움을 느끼셨을 것 같습니다. "오민식의 고민"문제에서 쉽게 해결하신분들은 아마 벨만포드 알고리즘의 작동원리를 잘 알고계셔서 풀었다고 생각이 됩니다. 

case : gg

DFS나 BFS를 통해 S노드에서 E노드를 방문할 수 없다면 그냥 gg를 출력하고 끝내면 됩니다.

void DFS(int now) {
     visit[now] = true;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i].first] == false) {
               DFS(vec[now][i].first);
          }
     }
}

    DFS(S);
     if (visit[E] == false) {
          cout << "gg\n";
          return 0;
     }

case : Gee

위의 언급한 타임머신, 웜홀 문제처럼 단지 cycle이 있는지 없는지를 통해 Gee를 출력하였다면 틀린 코드가 됩니다.

밑의 코드가 바로 그러한 코드입니다. 왜 이 코드가 틀렸는지 알아보도록 하겠습니다.

     // !!!!!!!!!!! 잘못된 코드 !!!!!!!!!!!!!!!!
     bool cycle = false;
     dist[S] = earn[S];
     for (int i = 1; i <= N ; i++) {
          for (int j = 0; j < N; j++) {
               for (const auto & x : vec[j]) {
                    int next = x.first; ll cost = x.second;
                    if (dist[j] != LLONG_MIN && dist[next] < dist[j] + cost) {
                         dist[next] = dist[j] + cost;
                         if (i == N)  dist[next] = LLONG_MAX;
                    }
               }
          }
     }
     if (cycle) cout << "Gee\n";
     else cout << dist[E] << "\n";
     // !!!!!!!!!!! 잘못된 코드 !!!!!!!!!!!!!!!!

밑의 케이스를 보면

만약 1번노드와 2번노드사이에 사이클이생겨 돈을 무한으로 벌 수 있다면

위의 잘못된 코드에서는 "Gee"를 출력할 것입니다. 하지만 사실 1에서 3으로 가는 경우가 끝이죠.

또다른 예시를 보겠습니다.

위의 사진의 경우는 사이클이 있고 해당 사이클에서 무제한으로 돈을 벌어서 3(E)번 노드에 방문할 수 있습니다.

그렇다면 첫번째 예시의 잘못된 경우를 어떻게 처리 할 수 있을까요?

사이클이 생기는 경우 해당 사이클이 생기는 노드에서 E번노드를 갈 수있는지 없는지 체크 하면 됩니다.

<방법 1>

1.  V-1번 반복문으로 모든 간선에대한 방문을통해서 해당 노드가 사이클이 있는지 없는지 확인
2.  V가 최대 100번밖에 되지 않음으로, 사이클이 생긴 노드에서 E번노드를 방문할 수 있는 없는지 모두 체크
   1. 성공했다면 "Gee" 출력
   2. 모든 노드에서 실패했다면 해당 노드들을 제외하고 최장거리 다시계산하여 dist[E] 출력

<방법 2>

1.  V-1번 반복문으로 모든 간선에 대한 방문을통해 해당 노드가 사이클이 있는지 없는지 확인
2.  다시한번 V-1 반복문으로 모든 간선에 대한 방문을통해 사이클이 있는 노드와 없는노드를 나누어서 처리
   1. dist[E] 설정된 최댓값이면 "Gee" 출력
   2. 그렇지 않으면 dist[E] 출력

  dist[S] = earn[S];
     for (int i = 1; i <= 2 * N; i++) {
          for (int j = 0; j < N; j++) {
               for (const auto & x : vec[j]) {
                    int next = x.first; ll cost = x.second;
                    if (dist[j] == LONG_MAX) dist[next] = LONG_MAX;
                    else if (dist[j] != LONG_MIN && dist[next] < dist[j] + cost) {
                         dist[next] = dist[j] + cost;
                         //cout << "dist[" << next << "] : " << dist[next] << endl;
                         if (i >= N) dist[next] = LONG_MAX;
                    }
               }
          }
     }
     // 사이클이 존재한다. 
     if (dist[E] == LONG_MAX) cout << "Gee\n";
     else cout << dist[E] << "\n";

(v가 100밖에 되지 않기때문에 다른 많은 방법들이 존재할것 같습니다.)

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
#define MAX_N 101
typedef long long ll;
vector<pair<int, int> > vec[MAX_N];
int earn[MAX_N];
ll dist[MAX_N];
bool visit[MAX_N];
void DFS(int now) {
     visit[now] = true;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i].first] == false) {
               DFS(vec[now][i].first);
          }
     }
}

int main() {
     int N, S, E, M;
     cin >> N >> S >> E >> M;
     for (int i = 0; i < N; i++) {
          dist[i] = LONG_MIN;
     }
     for (int i = 0; i < M; i++) {
          int s, e, c; cin >> s >> e >> c;
          vec[s].push_back({ e, -1 * c });
     }

     for (int i = 0; i < N; i++) {
          cin >> earn[i];
     }

     DFS(S);
     if (visit[E] == false) {
          cout << "gg\n";
          return 0;
     }

     for (int i = 0; i < N; i++) {
          for (int j = 0; j < vec[i].size(); j++) {
               vec[i][j].second += earn[vec[i][j].first];
          }
     }


     dist[S] = earn[S];
     for (int i = 1; i <= 2 * N; i++) {
          for (int j = 0; j < N; j++) {
               for (const auto & x : vec[j]) {
                    int next = x.first; ll cost = x.second;
                    if (dist[j] == LONG_MAX) dist[next] = LONG_MAX;
                    else if (dist[j] != LONG_MIN && dist[next] < dist[j] + cost) {
                         dist[next] = dist[j] + cost;
                         //cout << "dist[" << next << "] : " << dist[next] << endl;
                         if (i >= N) dist[next] = LONG_MAX;
                    }
               }
          }
     }
     // 사이클이 존재한다. 
     if (dist[E] == LONG_MAX) cout << "Gee\n";
     else cout << dist[E] << "\n";
}code

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

문제에서 "의존한다" 의 의미만 파악만 아마 어렵지 않게 풀 수 있을 것이다.

a가 b를 의존한다  = b에서 a로가는 단반향 간선이 존재한다 . 로 해석 할 수 있다.

첫 방문한 노드에대해서 방문cnt++ 를 해주었고,

첫방문과 유효한 노드방문이라면 max값을 갱신해주었다.

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX_N 10001
vector<pair<int, int>> vec[MAX_N];

class PQItem {
public:
     int n, cost, prevCost;
     PQItem(int n, int  cost) {
          this->n = n;
          this->cost = cost;
     }
     bool operator > (const PQItem & b) const {
          return this->cost > b.cost;
     }
};
priority_queue<PQItem, vector<PQItem>, greater<> > pq;

int dist[MAX_N];
bool visit[MAX_N];
pair<int,int> dijstra(int c) {
     int MAX = 0;
     int cnt = 1;
     pq.push(PQItem(c, 0));
     dist[c] = 0;
     visit[c] = true;
     while (!pq.empty()) {
          PQItem top = pq.top(); pq.pop();
          int n = top.n;
          int cost = top.cost;
          int prevConst = top.prevCost;
          if (dist[n] < cost) continue;
          MAX = max(MAX, cost);
          for (int i = 0; i < vec[n].size(); i++) {
               int nextN = vec[n][i].first;
               int nextCost = cost + vec[n][i].second;
               if (dist[nextN] > nextCost) {
                    dist[nextN] = nextCost;
                    if (visit[nextN] == false) {
                         visit[nextN] = true;
                         cnt++;
                    }
                    pq.push(PQItem(nextN, nextCost));
               }
          }
     }
     return { MAX,cnt };
}

int main() {
     ios::sync_with_stdio(false);  cin.tie(0);   cout.tie(0);
     int t; cin >> t;
     while (t--) {
          int n, d, c; cin >> n >> d >> c;
          for (int i = 0; i <= n; i++) {
               dist[i] = 1e9;
               visit[i] = false;
               vec[i].clear();
           }
          for (int i = 0; i < d; i++) {
               int a, b, w; cin >> a >> b >> w;
               vec[b].push_back({ a,w });
          }
          pair<int,int> result = dijstra(c);
          cout << result.second << " " << result.first << "\n";
     }
}

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

문제 설명이 너무 길고 약간 복잡하다. 그러나 이해만 잘하면 쉽게 풀 수 있는 문제이다.

최소한의 경로의 갯수 , 최소한의 경로의 합

을 만족시키기 위해서는 N개의 정점이 있을떄 N-1개의 간선을 사용하면 되고

N-1개의 간선의 합이 최소한의 경로가 되면 된다.

전체코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAX_N 1001
vector<pair<int,int>> vec[MAX_N];

class PQItem {
public:
     int n;
     int cost;
     PQItem(int n, int cost ) {
          this->n = n;
          this->cost = cost;
     }
     bool operator > (const PQItem & b) const {
          return this->cost > b.cost;
     }
};
priority_queue<PQItem, vector<PQItem>, greater<> > pq;

int dist[MAX_N];
int connect[MAX_N];
int connectCnt = 0;

void dijstra() {
     pq.push(PQItem(1, 0));
     dist[1] = 0;
     while (!pq.empty()) {
          PQItem top = pq.top(); pq.pop();
          int n = top.n;
          int cost = top.cost;
          if (dist[n] < cost) continue;
          for (int i = 0; i < vec[n].size(); i++) {
               int nextCost = vec[n][i].second + cost;
               if (dist[vec[n][i].first] > nextCost) {
                    dist[vec[n][i].first] = nextCost;
                    connect[vec[n][i].first] = n;
                    pq.push(PQItem(vec[n][i].first, nextCost));
               }
          }
     }
}


int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N >> M;
     for (int i = 0; i <= N; i++) {
          dist[i] = 1e9;
     }
     for (int i = 0; i < M; i++) {
          int a, b, w; cin >> a >> b >> w;
          vec[a].push_back({b,w});
          vec[b].push_back({a,w});
     }
     dijstra();
     cout << N - 1 << "\n";
     for (int i = 2; i <= N; i++) {
         cout << i << " " << connect[i] << "\n";
     }
}

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

각 간선의 가중치를 1로 보고 BFS를 돌아도 되고

PQ를 사용한 다익스트라 알고리즘을 사용해도 좋다.

다만 2중 포문으로 돌릴경우 O( n^2 ) 이므로 시간초과가 날 것이다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAX_N 20001
vector<int> vec[MAX_N];

class PQItem {
public:
     int n;
     int cost;
     PQItem(int n, int cost) {
          this->n = n;
          this->cost = cost;
     }
     bool operator > (const PQItem & b) const {
          return this->cost > b.cost;
     }
};
priority_queue<PQItem, vector<PQItem>, greater<> > pq;

int dist[MAX_N];
int num = -1, dis = 0, cnt = 0;

void dijstra() {
     pq.push(PQItem(1, 0));
     dist[1] = 0;
     while (!pq.empty()) {
          PQItem top = pq.top(); pq.pop();
          int n = top.n;
          int cost = top.cost;
          if (dist[n] < cost) continue;
          for (int i = 0; i < vec[n].size(); i++) {
               int nextCost = 1 + cost;
               if (dist[vec[n][i]] > nextCost) {
                    dist[vec[n][i]] = nextCost;
                    dis = max(dis, nextCost);
                    pq.push(PQItem(vec[n][i], nextCost));
               }
          }
     }
}


int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N >> M;
     for (int i = 0; i <= N; i++) {
          dist[i] = 1e9;
     }
     for (int i = 0; i < M; i++) {
          int a, b; cin >> a >> b;
          vec[a].push_back(b);
          vec[b].push_back(a);
     }
     dijstra();
     for (int i = 1; i <= N; i++) {
          if (dis == dist[i]) {
               if (num == -1) num = i;
               cnt++;
          }
     }
     cout << num << " " << dis << " " << cnt << "\n";
}

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

문제의 분류가 세그먼트 트리 with Lazy Propagation 이다. 밑의 문제를 풀 수 있다면, 세그먼트 트리를 구성하는 연산 기호만 잘 바꿔주면 쉽게 풀 수 있는 문제이다.

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

#include <iostream>
using namespace std;

#define MAX_N 100000
#define endl '\n'

int seg[MAX_N*4];
bool lazy[MAX_N*4];

void update_lazy(int now, int start, int end) {
     if (lazy[now] == true) {
          seg[now] = (end - start + 1) - seg[now];
          if (start != end) {
               lazy[now * 2] = (lazy[now * 2]) ? false : true;
               lazy[now * 2 + 1] = (lazy[now * 2 + 1]) ? false : true;
          }
          lazy[now] = false;
     }
}

void update_range(int now, int left, int right, int start, int end) {
     update_lazy(now, start, end);
     if (left > end || right < start) return;
     if (left <= start && end <= right) {
          seg[now] = (end - start + 1) - seg[now];
          if (start != end) {
               lazy[now * 2] = (lazy[now * 2]) ? false : true;
               lazy[now * 2 + 1] = (lazy[now * 2 + 1]) ? false : true;
          }
          return;
     }
     int mid = (start + end) / 2;
     update_range(now * 2, left, right, start, mid);
     update_range(now * 2 + 1, left, right, mid + 1, end);
     seg[now] = seg[now * 2] + seg[now * 2 + 1];
}

int query(int now, int left, int right, int start, int end) {
     update_lazy(now, start, end);
     if (left > end || right < start) return 0;
     if (left <= start && end <= right) {
          return seg[now];
     }
     int mid = (start + end) / 2;
     return(
          query(now * 2, left, right, start, mid) +
          query(now * 2 + 1, left, right, mid + 1, end)
          );
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N, Q; cin >> N >> Q;
     for (int i = 0; i < Q; i++) {
          int tag; cin >> tag;
          if (tag == 0) { // 반전
               int s, e; cin >> s >> e;
               update_range(1, s - 1, e - 1, 0, N - 1);
          }
          else { // on의 갯수
               int s, e; cin >> s >> e;
               cout << query(1, s - 1, e - 1, 0, N - 1) << endl;
          }
     }
}

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

문제 풀이 및 설명

문제의 분류는 세그먼트 트리 with Lazy Propagation 이다.

이문제를 처음 접했을때, lazy propagation에 대한 사전지식이 없다면 매우 어렵게 느낄 것이다. 

또한 구글링이나, 검색을통해 lazy propagation을 배우려고 할때에 세그먼트 트리의 update와 query의 작동방식을 알고 있다면, 금방  lazy propagation 도 이해할 수 있겠지만, 세그먼트 트리의 작동원리를 알지못하고 그저 코드를 외워서 문제를 풀어왔다면 lazy propagation풀이를 봐도 이해하지 못할 것이다. 이문제의 유형을 처음 접했다면, lazy propagation을 먼저 검색해보고, lazy propagation이 이해가 가지 않는다면, 세그먼트 트리를 다시 공부 할 필요가 있다. (다른 수많은 블로그에 엄청 자세하게 나와있다)

전체 코드

#include <iostream>
using namespace std;

#define MAX_N 1000001
#define endl '\n'
typedef long long ll;
ll seg[MAX_N * 4];
ll lazy[MAX_N * 4];

void update_tree(int now, int target, int start, int end, ll value) {
     if (target > end || target < start) return;
     if (start == end) {
          seg[now] = value;
          return;
     }
     int mid = (start + end) / 2;
     update_tree(now * 2, target, start, mid, value);
     update_tree(now * 2 + 1, target, mid + 1, end, value);
     seg[now] = seg[now * 2] + seg[now * 2 + 1];
}

void update_lazy(int now,int start, int end){
     if (lazy[now] != 0) {
          seg[now] += (end - start + 1) * lazy[now];
          // 자신의 자식 리프노드의 갯수만큼 segment tree에 더해줌
          if (start != end) { // 만약 리프노드가 아니라면
               lazy[now * 2] += lazy[now];
               lazy[now * 2 + 1] += lazy[now];
               // 자신의 자식들의 노드에게 lazy 전달
          }
          lazy[now] = 0; // 해당 세그먼트 트리 노드에 대해서 업데이트 완료 했음으로 lazy 초기화
     }
}

void update_range(int now, int left, int right, int start, int end, ll value) {
     update_lazy(now, start, end);
     if (left > end || right < start) return;
     if (left <= start && end <= right) {
          seg[now] += (end - start + 1) * value;
          if (start != end) {
               lazy[now * 2] += value;
               lazy[now * 2 + 1] += value;
          }
          return;
     }
     int mid = (start + end) / 2;
     update_range(now * 2, left, right, start, mid, value);
     update_range(now * 2 + 1, left, right, mid + 1, end, value);
     seg[now] = seg[now * 2] + seg[now * 2 + 1];
}

ll query(int now, int left, int right, int start, int end) {
     update_lazy(now, start, end);
     if (left >end || right < start) return 0;
     if (left <= start && end <= right) {
          return seg[now];
     }
     int mid = (start + end) / 2;
     return (
          query(now * 2, left, right, start, mid) +
          query(now * 2 + 1, left, right, mid + 1, end)
          );
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N, M, K;
     cin >> N >> M >> K;
     for (int i = 0; i < N; i++) {
          ll data; cin >> data;
          update_tree(1, i, 0, N - 1, data);
     }
     for (int i = 0; i < M + K; i++) {
          int tag; cin >> tag;
          if (tag == 1) { // b ~ c , d update
               int b, c; ll value;
               cin >> b >> c >> value;
               update_range(1, b - 1, c - 1, 0, N - 1, value);
          }
          else { // b ~ c 구간합
               int b, c; cin >> b >> c;
               cout << query(1, b - 1, c - 1, 0, N - 1) << endl;
          }
     }
}

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

이 문제를 해결 하기 위해서는 우선 밑의 문제를 풀 수 있어야 한다.

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

위의 문제와 비슷한 아이디어로 풀긴 하지만 좀 더 까다롭다.

(초기 MST를 구성하면서, 모든 정점을 방문하지 못한다면, -1를 출력하면 된다.)

{u , v , w} 의 정보를 갖는 새로운 간선을 삽입 할 경우

(기존 mst의 간선의 총합)-(u와v의 간선중 가장 큰 경로)+(w)

가 기존 (기존 mst의 간선의 총합) 보다 큰 것중에 가장 작은 값이 곧 답이 된다.

그러나, (u와v의 간선중 가장 큰 경로) == (w)

인경우를 생각 해보면 결국,

(기존 mst의 간선의 총합)-(u와v의 간선중 가장 큰 경로)+(w) == (기존 mst의 간선의 총합)

이 되어버리기 때문에, 실제로는 다른 mst가 존재함에도 불구하고 conitnue 하게 된다.

그렇기 때문에, 첫번째로 큰 간선이 w와 같은 경우에

두번째로 큰 간선을 찾아서 똑같이 적용시키면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
#include <cstring>
using namespace std;

#define MAX_N 50001
#define MAX_PAR 20
#define SWAP(a,b) {int t= b; b = a; a = t;}
typedef long long ll;

int par[MAX_N][MAX_PAR]; // 부모 배열
int MAX[MAX_N][MAX_PAR]; // 최댓값 배열
int depth[MAX_N]; // 깊이 배열
bool visit[MAX_N]; // DFS 체크

// 입력 순서대로 우선 저장될 edge 정보
class edge {
public:
     int u, v, w;
     edge() {}
     edge(int u, int v, int w) {
          this->u = u;
          this->v = v;
          this->w = w;
     }
};
vector<edge> edges; // 입력 순서대로 저장

// MST를 위한 간선
vector<pair<int, int>> map[MAX_N];

// PQ에 들어갈 아이템 ( cost 순으로 정렬 됨 )
class PQItem {
public:
     int now, nowDepth, prev, prevDist;
     PQItem() {}
     PQItem(int now, int nowDepth, int prev, int prevDist) {
          this->now = now;
          this->nowDepth = nowDepth;
          this->prev = prev;
          this->prevDist = prevDist;
     }
     bool operator < (const PQItem & b) const {
          return this->prevDist < b.prevDist;
     }
     bool operator > (const PQItem & b) const {
          return this->prevDist > b.prevDist;
     }
};
priority_queue<PQItem, vector<PQItem>, greater<> > pq;

// 입력받을 V, E
int V, E;
ll MST() {
     int cnt = 0, ret = 0; 
     pq.push(PQItem(1, 0, 1, 0)); // 1번노드부터 pq push
     while (!pq.empty()) {
          PQItem top = pq.top(); pq.pop();
          int now = top.now;
          int prev = top.prev;
          int prevDist = top.prevDist;
          int nowDepth = top.nowDepth;
          if (visit[now]) continue;
          par[now][0] = prev; // 1번째 부모
          MAX[now][0] = prevDist; // 부모와의 dist
          depth[now] = nowDepth; // 현재 depth
          ret += prevDist; // mst 간선의 총합을 위한 리턴값
          visit[now] = true; // visit 체크
          cnt++; // MST의 존재여부 파악을 위함
          for (int i = 0; i < map[now].size(); ++i) {
               if (!visit[map[now][i].first]) {
                    pq.push(PQItem(map[now][i].first, nowDepth + 1, now, map[now][i].second));
               }
          }
     }
     if (cnt != V) ret = -1; // mst가 존재하지않는다 ( = 한 정점에서 모든 정점을 방문 할 수 없다 )
     return ret;
}

// lca 알고리즘
int LCA(int x, int y) {
     if (depth[x] > depth[y]) SWAP(x, y);

     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) {
               y = par[y][i];
          }
     }
     if (x == y) return x;
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     return par[x][0];
}

// x노드와 y노드 사이의 간선의 최댓값 리턴
int getMax(int x, int y) {
     int lca = LCA(x, y);
     int ret = -1;
     int x_to_lca = depth[x] - depth[lca];
     int y_to_lca = depth[y] - depth[lca];
     for (int i = 19; i >= 0; i--) {
          if (x_to_lca >= (1 << i)) {
               ret = max(ret, MAX[x][i]);
               x_to_lca -= (1 << i);
               x = par[x][i];
          }
     }

     for (int i = 19; i >= 0; i--) {
          if (y_to_lca >= (1 << i)) {
               ret = max(ret, MAX[y][i]);
               y_to_lca -= (1 << i);
               y = par[y][i];
          }
     }
     return ret;
}

// x노드와 y 노드 사이의 2번째로 큰 ( prevMax보다 첫번째로 작은 ) 값 리턴
// O(N)으로 탐색했음 ( 더좋은 방법이 있을 것 같음 )
int getSecondMax(int x, int y, int prevMax) {
     int lca = LCA(x, y);
     int x_to_lca = depth[x] - depth[lca];
     int y_to_lca = depth[y] - depth[lca];
     int ret = -1;
     for (int i = 0; i < x_to_lca; ++i) {
          if (MAX[x][0] < prevMax) {
               ret = max(ret, MAX[x][0]);
          }
          x = par[x][0];
     }

     for (int i = 0; i < y_to_lca; ++i) {
          if (MAX[y][0] < prevMax) {
               ret = max(ret, MAX[y][0]);
          }
          y = par[y][0];
     }
     return ret;
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0); cout.tie(0);
     cin >> V >> E;
     for (int i = 0; i < E; ++i) {
          int a, b, w; cin >> a >> b >> w;
          edges.push_back(edge(a, b, w));
          map[a].push_back({ b,w });
          map[b].push_back({ a,w });
     }

     ll minimum = MST();
     if (minimum == -1) {
          cout << -1 << "\n";
          return 0;
     }

     for (int i = 1; i <= 19; ++i) {
          for (int j = 1; j <= V; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
               MAX[j][i] = max(MAX[j][i - 1], MAX[par[j][i - 1]][i - 1]);
          }
     }

     int ans = INT_MAX;
     for (int i = 0; i < E; ++i) {
          int u, v, w;
          u = edges[i].u;
          v = edges[i].v;
          w = edges[i].w;
          int maxE = getMax(u, v);
          // 가장 큰 값과 비교
          if (minimum - maxE + w > minimum) {
               if (ans > minimum - maxE + w) ans = minimum - maxE + w;
          }
          // 가장 큰 값이 현재 삽입하려는 간선의 weight와 같다면
          // 두번 째로 큰 간선을 찾는다
          else if (minimum - maxE + w == minimum) {
               int secondMaxE = getSecondMax(u, v, maxE);
               // 찾았 다면
               if (secondMaxE != -1) {
                    if (ans > minimum - secondMaxE + w) ans = minimum - secondMaxE + w;
               }
          }
     }
     if (ans == INT_MAX) cout << -1 << "\n";
     else cout << ans << "\n";
}

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

MST 알고리즘 ( prim 알고리즘 사용 ) + LCA 알고리즘을 이용한 문제풀이가 가능하다.

우선 사용될 변수(배열)들은 다음과 같다.

bool visit[MAX_N]; // for mst
int par[MAX_N][21]; // 부모 배열
int dist[MAX_N][21]; // 두노드간의 거리의 최대 간선의 weight가 저장될 배열
int depth[MAX_N]; // for lca 

입력된 간선들로 MST를 만들면서 depth, dist, par 배열 완성하게 되면

실제로 MST를 이루는 간선의 갯수는 결국 N - 1 개가 된다.

다음의 예제를 통한 완성 된 결과를 보자

위의 결과로 가장 최선의 MST 는 10 이다

그럼 첫번째 간선에 대해서 확인해보자.

1번과 2번을 이어주게되면 

길이 4 또는 2를 제거해야 하는데 당연히 4를 제거 해야 5가 포함된 mst를 완성할 수 있다.

(즉, 1번과 2번노드사이의 최대 길이 경로 하나를 삭제하면 된다 )

다른 케이스를 확인해보자.

이경우에는 길이 4의 간선을 삭제( 4번노드과 1번노드 사이의 가장 긴 경로의 간선 )

을 하게되면 답이 10( 원래 mst ) - 4 ( 삭제된 간선 ) + 9 ( 삽입된 간선 ) = 15. 이된다.

< 전체 코드 >

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <algorithm>
using namespace std;

#define MAX_N 200001
#define swap(a,b) {int t= b ; b = a; a = t;}


// DFS( mst )를 위한 vector
vector<pair<int, int> > map[MAX_N];

// 간선을 순서대로 저장하기위한 클래스
class edge {
public:
     int u, v, w;
     edge() {}
     edge(int u, int v, int w) {
          this->u = u;
          this->v = v;
          this->w = w;
     }
};

// 순서대로 저장되어있는 vector
vector<edge> edges;

bool visit[MAX_N]; // for mst
int par[MAX_N][21]; // 부모 배열
int dist[MAX_N][21]; // 두노드간의 거리의 최대 간선의 weight가 저장될 배열
int depth[MAX_N]; // for lca 

// pq에 들어갈 item ( cost 순으로 정렬되어 pop 됨 )
class pqItem {
public:
     int n, cost, prev, depth;
     pqItem() {}
     pqItem(int n, int cost, int prev, int depth) {
          this->n = n;
          this->cost = cost;
          this->prev = prev;
          this->depth = depth;
     }
     bool operator > (const pqItem & b) const {
          return this->cost > b.cost;
     }
     bool operator < (const pqItem & b) const {
          return this->cost < b.cost;
     }
};
// cost 가 제일 작은 것이 pop 됨.
priority_queue< pqItem, vector<pqItem>, greater<> > pq;

// mst 를 돌면서, 부모의 정보와, dist 정보를 저장
long long mst() {
     long long ret = 0;
     pq.push(pqItem(1, 0,1,0));
     while (!pq.empty()) {
          pqItem front = pq.top(); pq.pop();
          
          int now = front.n;
          int cost = front.cost;
          int nowDepth = front.depth;
          int prev = front.prev;
          
          if (visit[now]) continue;
          visit[now] = true;
          
          ret += cost;
          par[now][0] = prev; // 2^0 부모 설정
          dist[now][0] = cost; // 2^0 부모까지의 최대 거리 설정
          depth[now] = nowDepth; // lca 알고리즘을 위한 depth 설정
          for (int i = 0; i < map[now].size(); i++) {
               if (visit[map[now][i].first] == false) {
                    pq.push(pqItem(map[now][i].first, map[now][i].second, now, nowDepth + 1));
               }
          }
     }
     return ret;
}


int lca(int x, int y) {
     if (depth[x] > depth[y]) swap(x, y);
     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) {
               y = par[y][i];
          }
     }
     if (x == y) return x;
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     return par[x][0];
}


int main() {
     ios::sync_with_stdio(false);
     cin.tie(0); cout.tie(0);
     int N, M;
     cin >> N >> M;
     for (int i = 0; i < M; i++) {
          int u, v, w; cin >> u >> v >> w;
          map[u].push_back({ v,w });
          map[v].push_back({ u,w });
          edges.push_back( edge(u, v, w) );
     }
     long long minimum = mst();
     for (int i = 1; i <= 19; i++) {
          for (int j = 1; j <= N; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
               dist[j][i] = max(dist[j][i-1],dist[par[j][i - 1]][i - 1]);
          }
     }

     for (int i = 0; i < edges.size(); i++) {
          int u = edges[i].u;
          int v = edges[i].v;
          int w = edges[i].w;
          long long ret = minimum + w;
          int lca_node = lca(u, v);
          int u_to_lca = depth[u] - depth[lca_node];
          int v_to_lca = depth[v] - depth[lca_node];
          int maxAns = -1;
          for (int j = 19; j >= 0; j--) {
               if (u_to_lca >= (1 << j)) {
                    maxAns = max(maxAns, dist[u][j]);
                    u_to_lca -= (1 << j);
                    u = par[u][j];
               }
          }
          for (int j = 19; j >= 0; j--) {
               if (v_to_lca >= (1 << j)) {
                    maxAns = max(maxAns, dist[v][j]);
                    v_to_lca -= (1 << j);
                    v = par[v][j];
               }
          }
          cout << ret - maxAns << "\n";
     }
}