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 上寫不到這題喔
非常抱歉 > <