UVA 1664 - Conquer a New Region（並查集）

UVA 1664 - Conquer a New Region（並查集）

該題巧妙的運用了並查集，運用了類似於最小生成樹算法的過程 ，通過該題可以對並查集有一個更深的理解 。

由於i和j唯一通路上容量的最小值為該兩點的容量，求一個點到其他所有點的容量最大值 。

首先，解決兩點的容量問題 ，我們將所有邊從大到小排序，然後從大到小枚舉，我們假設根結點就是要找的城市中心點，那麼當又加入一條邊時，該邊的兩個頂點所在的集合設為A、B，集合A、B的頂點a、b，要讓誰當中心點呢？ 易知：無論誰當中心點，它與另一個集合中任一點的容量都為該邊長度（因為是從大到小枚舉的）。

那麼為了求出總容量，我們要維護一些值，用空間換時間 。 維護每個頂點的總容量sum[i]，維護每個頂點與之相連的頂點數量，cnt[i]，當前答案ans 。

那麼對於a、b點，如果以a為中心，總容量為sum[a] + cnt[b] * e[i].c 。 反之亦然，哪個量大，則以哪個點為城市中心，也就是並查集的根結點 。

該題的巧妙之處在於，將答案結點維護成並查集的根結點，快速的找出一個集合中的城市中心 。

並查集用了路徑壓縮之後其實已經很快了，沒有必要在改變樹的高度，因為那樣會改變根結點，不僅寫起來麻煩，還丟掉了許多很好的特性 。

該題就是通過這些特性，維護一些重要的量以達到快速求解的目的 。 請讀者細細品味 。

細節參見代碼：

#include
using namespace std;
typedef long long ll;
const int maxn = 200000 + 5;
int n,m,p[maxn];
ll sum[maxn],cnt[maxn];
struct Edge{
    ll a,b,c;
    bool operator < (const Edge& rhs) const {
        return c > rhs.c;
    }
}e[maxn];
int findd(int x) { return p[x] == x ? x : p[x] = findd(p[x]); }
ll solve() {
    for(int i=1;i<=n;i++) { p[i] = i ; sum[i] = 0 ; cnt[i] = 1; }
    ll ans = 0;
    sort(e,e+n-1);
    for(int i=0;i