UVA 12275 Sensor network ( 增量最小瓶頸生成樹 )

UVa Online Judge
和 UVA 1395 Slim Span是同一個問題，但測資加強
UVA 1395 Slim Span ( 水題最小瓶頸生成樹 ) - 0w1
因為允許18秒，所以試了看看哪裏可以做小優化，發現我每次加入一個邊都有重新排序，這是無意義的，做第一次就行了。但搬出來還是TLE。又注意到這題的輸入限制 1 ≤ w ≤ 2 ^ 15 = 32768，所以排序後如果我們不重複檢查一樣邊權的邊，是可以做到 O( m * lg m + m * min( m, w ) ) 的複雜度。最差情況的n = 350, m = 350 * 349 / 2 = 61075, w = 32768 代入概算一下是 20億，但實際上計算量大概會是一半的，常數處理好就能這樣水過。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 350 + 2;
const int MAXM = MAXN * MAXN;
const int INF = 1e9;

struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}
    bool operator < (const Edge &oth) const{
        return w < oth.w;
    }
} es[MAXM];

int n, m;

struct UnionFind{
    int fa[MAXN];
    void init(int n){
        for(int i = 0; i <= n; ++i)
            fa[i] = i;
    }
    int find(int x){ return fa[x] == x ? x : fa[x] = find( fa[x] ); }
    bool unite(int a, int b){
        int x = find( a ), y = find( b );
        if( x == y ) return false; // no changes made
        fa[x] = y; return true;
    }
} uf;

struct Kruskal{ // es => 1 - idx
    void init(){
        uf.init( n );
    }
    int solve(int k){ // starts picking from the k'th smallest
        init();
        int picked = 0;
        int cur;
        for(cur = k; cur < m; ++cur){
            if( uf.unite( es[ cur ].u, es[ cur ].v ) )
                ++picked;
            if( picked == n - 1 ) break;
        }
        if( picked < n - 1 ) return INF; // impossible
        return es[ cur ].w - es[ k ].w; // maxw - minw
    }
} mst;

void solve(){
    sort( es, es + m ); // sort edges only once for every test case
    int ans = INF;
    for(int i = 0; i < m; ++i){
        if( i && es[i].w == es[i - 1].w ) continue; // 1 <= w <= ( 1 << 15 )
        ans = min( ans, mst.solve( i ) );
    }
    printf("%d\n", ans);
}

int main(){
    while( scanf("%d%d", &n, &m) == 2 && n + m ){
        for(int i = 0; i < m; ++i)
            scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].w);
        solve();
    }
    return 0;
}

不知道這題之所以設邊權的限制( 還剛好是2的冪次好算複雜度 )，是不是有意圖讓我們這樣水過，但事實上是存在 O( n * m ) 的算法，在uva judge上的運行時間甚至可以到上面暴力法的百分之一以下。
基本上是利用增量最小生成樹的經典算法的概念，只保存當前的最小瓶頸生成樹，動態的去環和加邊。
關於增量最小生成樹可以看
生成樹相關問題 -- 訓練指南 - 0w1
對這題具體來說，可以用尺取法的思維，邊由小到大丟進去，當環產生時根據生成樹的迴路性質，產生環時馬上捨棄環裡權值最小的邊，一步一步更新答案。實作上，我先跑一遍把最小瓶頸生成樹做出來，然後再利用一個迴圈拜訪那些還沒用過的邊。我是用BFS尋找環裡權值最小的邊，而且是在把新邊丟進去之前做，因為樹上任兩點的最短路徑是唯一的，若給樹上 u, v兩點加邊，這個迴路減去新的邊一定是原本樹上 u, v的最短路徑。過程中記錄每個節點的前驅，最後再反向尋找最小後刪除。更新答案的部分是我做的效率最差的部分，暴力DFS重新尋找生成樹上的最大和最小權，應該有更好的做法，但我覺得這部分的理論複雜度 O( n )差不多就不管了。
雖然調用了很多STL追求可讀性，但我功力不足，常數太大還是跑了 6秒，慚愧。。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 350 + 2;
const int MAXM = MAXN * MAXN / 2;
const int INF = 1e9;

struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}
    bool operator < (const Edge &oth) const{
        return w < oth.w;
    }
} es[MAXM];

int n, m;
vector<Edge> G[MAXN];
int wei[MAXN][MAXN]; // weight of edge u <-> v

struct UnionFind{
    int fa[MAXN];
    void init(int n){
        for(int i = 0; i <= n; ++i)
            fa[i] = i;
    }
    int find(int x){ return fa[x] == x ? x : fa[x] = find( fa[x] ); }
    bool unite(int a, int b){
        int x = find( a ), y = find( b );
        if( x == y ) return false;
        fa[ x ] = y; return true;
    }
} uf;

struct Kruskal{
    int vis[MAXM];
    void init(){
        uf.init( n );
        for(int i = 0; i <= n; ++i)
            G[i].clear();
        memset( vis, 0, sizeof(vis) );
    }
    int findAndDelMinwEdgeOnPath(int a, int b){ // bfs
        vector<int> visited( MAXN ), pre( MAXN, -1 );
        queue<int> que;
        que.push( a );
        visited[ a ] = 1;
        int minu, minv;
        while( !que.empty() ){
            int u = que.front(); que.pop();
            for(int i = 0; i < G[u].size(); ++i){
                int v = G[u][i].v;
                if( visited[ v ] ) continue;
                visited[ v ] = 1;
                pre[ v ] = u;
                if( v == b ){
                    int res = INF;
                    while( u != -1 ){
                        if( res > wei[ u ][ v ] ){
                            res = wei[ u ][ v ];
                            minu = u, minv = v;
                        }
                        u = pre[ u ], v = pre[ v ];
                    }
                    for(auto it = G[minu].begin(); it != G[minu].end(); ++it)
                        if( it->v == minv ){
                            G[ minu ].erase( it );
                            break;
                        }
                    for(auto it = G[minv].begin(); it != G[minv].end(); ++it)
                        if( it->v == minu ){
                            G[ minv ].erase( it );
                            break;
                        }
                    return res;
                }
                que.push( v );
            }
        }
        assert( false ); // should not come to here
    }
    void findMinMax(int u, int fa, int &mn, int &mx){
        for(int i = 0; i < G[u].size(); ++i){
            int v = G[u][i].v;
            if( v == fa ) continue;
            mn = min( mn, G[u][i].w );
            mx = max( mx, G[u][i].w );
            findMinMax( v, u, mn, mx );
        }
    }
    int solve(){
        sort( es, es + m );
        int minw = INF, maxw = 0, picked = 0;
        for(int i = 0; i < m; ++i){
            if( uf.unite( es[i].u, es[i].v ) ){
                G[ es[i].u ].push_back( Edge( es[i].u, es[i].v, es[i].w ) );
                G[ es[i].v ].push_back( Edge( es[i].v, es[i].u, es[i].w ) );
                vis[ i ] = 1;
                minw = min( minw, es[i].w );
                maxw = max( maxw, es[i].w );
                if( ++picked == n - 1 ) break;
            }
        }
        assert( picked == n - 1 );

        int mindiff = maxw - minw;
        for(int i = 0; i < m; ++i) if( !vis[ i ] ){
            int minwOnCycle = findAndDelMinwEdgeOnPath( es[i].u, es[i].v );
            G[ es[i].u ].push_back( Edge( es[i].u, es[i].v, es[i].w ) );
            G[ es[i].v ].push_back( Edge( es[i].v, es[i].u, es[i].w ) );
            minw = INF, maxw = 0;
            findMinMax( 0, -1, minw, maxw );
            mindiff = min( mindiff, maxw - minw );
        }
        return mindiff;
    }
} mst;

void solve(){
    mst.init();
    printf("%d\n", mst.solve());
}

int main(){
    while( scanf("%d", &n) == 1 && n ){
        scanf("%d", &m);
        for(int i = 0; i < m; ++i){
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            wei[ u ][ v ] = wei[ v ][ u ] = w;
            es[ i ] = Edge( u, v, w );
        }
        solve();
    }
    return 0;
}