[Baekjoon - 18199] Commemorative Race

난이도: Platinum II

 

태그

• Topological Sort
• Maximum Distance in Directed Acyclic Graph

 

풀이

1. 간선을 자르지 않을 때, 참가자들이 타게 될 최장경로들은?

DAG이기 때문에, 위상정렬 + 거리 계산을 사용해서 최장경로를 계산할 수 있습니다.

 

실제 최단경로에 포함되는 간선들은 '가장 멀리 있는 정점'에 도달할 수 있는 정점들 사이의 간선이 되겠죠.

// 물론 그 간선이 유의미하게 사용되어야 합니다. 즉, dis[v]+1 = dis[w]여야 하죠.

 

2. 자를 때 답에 유의미한 영향을 끼치는 간선들은?

만약, 어떤 간선을 잘랐는데 하나 이상의 최장경로가 유지되었다고 해봅시다.

그럼, 그 최장경로 때문에 답에 변화가 없을 것입니다.

 

이를 반대로 말하면, 답에 유의미한 영향을 끼치는 간선들은 모든 최장경로에 포함되는 간선이어야 합니다.

(v, w) 간선이 이를 만족하려면 아래 조건을 모두 만족해야 합니다.

• 거리가 dis[v]이면서 최장경로에 포함되는 정점이 v밖에 없다.
• 거리가 dis[w]이면서 최장경로에 포함되는 정점이 w밖에 없다.
• dis[v]+1 = dis[w]이다.

 

3. 그 간선들이 잘릴 때의 답은?

그 간선이 잘린 뒤에는, 더 이상 간선을 자를 수 없습니다.

그럼, (v, w)를 제외한 다른 간선들 중 (v, u)를 골랐다고 합시다.

그 뒤로는 그냥 u에서 최대한 멀리 가는 경로를 찾아주면 됩니다.

 

이는 모든 간선을 뒤집고 위상 정렬을 돌려주면서 구해줄 수 있습니다.

 

4. 코드

vector<int> adj[100020], jda[100020]; int cnt[100020];
int dis[100020]; pi2 srt[100020];
int num[100020];
 
bool mxd[100020];
vector<int> pos[100020];
 
void Main(){
    int n, m; cin >> n >> m;
    while (m--){
        int v, w; cin >> v >> w;
        adj[v].push_back(w); cnt[w] += 1;
        jda[w].push_back(v);
    }
    queue<int> q;
    for (int i = 1; i <= n; i++){
        if (cnt[i] == 0){ q.push(i); }
    }
    while (!q.empty()){
        int now = q.front(); q.pop();
        srt[now] = {dis[now], now};
        for (int nxt : adj[now]){
            cnt[nxt] -= 1; if (cnt[nxt] == 0){ q.push(nxt); }
            dis[nxt] = max(dis[nxt], dis[now]+1);
        }
    }
    sort(srt+1, srt+n+1, [](pi2 a, pi2 b){ return a > b; });
    for (int v = 1; v <= n; v++){
        for (int w : jda[v]){ cnt[w] += 1; }
    }
    for (int i = 1; i <= n; i++){
        if (cnt[i] == 0){ q.push(i); }
    }
    while (!q.empty()){
        int now = q.front(); q.pop();
        //cout << "TOPO2 " << now << ' ' << num[now] << endl;
        for (int nxt : jda[now]){
            cnt[nxt] -= 1; if (cnt[nxt] == 0){ q.push(nxt); }
            num[nxt] = max(num[nxt], num[now]+1);
        }
    }
    int ans = srt[1].fr, mx = srt[1].fr;
    for (int i = 1; i <= n; i++){
        int d = srt[i].fr, v = srt[i].sc;
        if (dis[v] == mx){ mxd[v] = 1; }
        else{
            for (int w : adj[v]){
                if (dis[v]+1 == dis[w] && mxd[w]){ mxd[v] = 1; }
            }
        }
        if (mxd[v]){ pos[d].push_back(v); /*cout << "POS " << d << ' ' << v << endl;*/ }
    }
    for (int i = 0; i < mx; i++){
        if (pos[i].size() == 1 && pos[i+1].size() == 1){
            int v = pos[i][0], w = pos[i+1][0];
            //cout << "CHK " << v << ' ' << w << endl;
            int res = 0;
            for (int u : adj[v]){
                if (u == w){ continue; }
                res = max(res, num[u]+1);
                //cout << "RES " << i << ' ' << num[u] << endl;
            }
            ans = min(ans, i+res);
        }
    }
    cout << ans;
}