Sep 10, 2018

[TOJ][420] C. 藏寶圖

今天來講講自己出的題目好了這題是我在今年（2018）六月時排名賽出的題目搞測資搞了一個禮拜，結果賽中只有一個人有認真寫過QQ

題目

題意略，總之，就是給定一張圖，求這張圖的 MST 的樹直徑 MST 怎麼做？我這邊選用 Kruskal （當然也可以用 Prim 做啦，只是個人習慣寫 Kruskal）

先備知識

在提 Kruskal 前，我們先講講 MST 到底是什麼吧

最小生成樹

MST 的正式全名為「最小生成樹」所謂的生成樹就是把這張圖拔掉一些邊後，這張圖沒有環以及所有點都有聯通 也就是說：假設目前有張圖 $G$ 的子圖 $T$ ，且 $T$ 上任意兩點間只有剛好一條路徑，則稱 $T$ 為 $G$ 的其中一顆生成樹

而當一張圖 $G$ 的子圖 $T1$ 且 $T1$ 為 $G$ 之最小生成樹，則代表找不到另外其他同為生成樹的子圖 $T'$ 其邊權重總和比 $T1$ 還要來得大時，就稱 $T1$ 為圖 $G$ 的最小生成樹

樹直徑

那麼樹直徑又是什麼呢？通常樹直徑就是一棵樹上的任意點對的最長距離

作法

Kruskal

我先講講Kruskal是什麼好了

按照MST的定義，有個很直觀的想法

先按照邊的權重對於所有邊由小到大排序過
依序取出所有邊，假設這個邊的兩端還不在同一個聯通塊內，則把這個邊加進去 MST 中

至於要怎麼確認這兩個點是不是屬於同一個聯通塊內呢？總不可能暴力dfs吧這時就要搬另外一個資料結構出來了，叫並查集(disjoint set) 詳細內容可以看這篇

樹直徑

樹直徑作法通常有兩個：

dfs時紀錄離當前點 $n_i$ 最遠的點 $u_i$ 以及次遠的點 $v_i$ ，則所有點 $n_i~u_i + n_i~v_i$ 的距離之最大值就是樹直徑
先對任意一個點 dfs 一次，找出離該點最遠的點再dfs一次，離該點最遠的最大值就是答案

作法1還挺好瞭解的，只是實作上可能會出包作法2有點費時間，但是很好寫

code

總而言之，我的 code 長這樣是用 Kruskal + dsu 路徑壓縮 + 樹直徑方法二寫的

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

#define maxN 1000005
typedef pair < int, int > pii;
typedef long long LL;
#define pb push_back
#define F first
#define S second

struct node{
    int u, v, w;
};

inline bool cmp ( node a, node b ){
    return a.w < b.w;
}

int dis[maxN];
LL dist[maxN];
vector < node > edges;
vector < pii > mst[maxN];

inline void init ( void ){
    for ( int i = 0 ; i < maxN ; i++ )
        dis[i] = i;
}

int find ( int n ){
    return dis[n] == n ? n : dis[n] = find ( dis[n] );
}

inline void Union ( int a, int b ){
    dis[find ( a )] = find ( b );
}

inline bool same ( int a, int b ){
    return find ( a ) == find ( b );
}

inline void Kruskal ( void ){
    sort ( edges.begin(), edges.end(), cmp );
    for ( auto &i: edges ){
        if ( same ( i.u, i.v ) )
            continue;
        Union ( i.u, i.v );
        mst[i.u].pb ( pii ( i.v, i.w ) );
        mst[i.v].pb ( pii ( i.u, i.w ) );
    }
}

void dfs ( int n, int p ){ // 樹直徑
    for ( auto i: mst[n] ){
        if ( i.F == p )
            continue;
        dist[i.F] = dist[n] + i.S;
        dfs ( i.F, n );
    }
}

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, m, u, v, w, t, idx, now;
    LL ma = -1;
    cin >> n >> m;
    init();
    while ( m-- ){
        cin >> u >> v >> w;
        edges.pb ( node { u, v, w } );
    }

    Kruskal();

    dfs ( 0, -1 );
    for ( int i = 0 ; i < n ; i++ )
        if ( ma < dist[i] )
            ma = dist[i], idx = i;

    dist[idx] = 0;
    dfs ( idx, -1 );
    ma = -1;
    for ( int i = 0 ; i < n ; i++ )
        ma = max ( ma, dist[i] );

    cout << ma << '\n';
}

後記

我這一篇文我有種我是在寫 disjoint set 教學的錯覺覺得累大半篇幅都是在教 disjoint set 看來原始 md 檔要破 300 行了呢（倒地

然後還有那一堆數學式子，看到頭都在痛我個人還蠻喜歡寫那些東西的看起來很猛（就是中二啦 = = 不過常常寫到一半會開始懷疑我沒事寫那麼難動幹嘛沒事虐待自己幹嘛話雖如此不過還是寫完了啦XD

更新(2019/03/06)

雖然說不是最近的事了，不過我想我還是提一下好了因為去年十月跟社團上有一點不高興，我要求學弟把我出的題目下架了所以目前在 TOJ 上寫不到這題喔非常抱歉 > <