[HDU 1512][Heap][Heuristic Merge] Monkey Kings

原題連結
懂啟發式合併之後這題就很單純了。
對於每個連通分量可以用一個priority_queue去做維護，快速查詢兩隻猴子在哪個連通分量可以用並查集。我們讓並查集的頭(就是最老爸(?)的那個點）去儲存該連通分量的所有點。

問題來了，如何好好合併兩個連通分量讓複雜度不會爛掉呢？
這就是啟發式合併幫忙解決的問題；我們每次合併時，都將size小的往size大的max heap裡丟，這樣做的話總體複雜度會是多少呢？

對於每一個元素，當他被拿出來丟給其他heap合併之後，他所在的heap size至少會變成原先的兩倍。因此每個元素不會被拿出來丟超過logn次，也就是插入這個操作最多執行O(nlogn)次。

這樣的總體時間複雜度就是O(nlgnlgn)。
實際表現也很不錯，時限5000MS只用了858MS。

#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=100000+5;
int fa[maxn];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
priority_queue<int> pq[maxn];
int merge(int& a,int& b)
{
    if(pq[a].size() < pq[b].size() ) swap(a,b);
    while(pq[b].size()) {pq[a].push(pq[b].top());pq[b].pop();}
    return pq[a].top();
}
int main()
{
    int N,M;
    while(scanf("%d",&N)==1 && N)
    {
        for(int i=1,x;i<=N;i++) {fa[i]=i;scanf("%d",&x);while(pq[i].size())pq[i].pop();pq[i].push(x);}
        scanf("%d",&M);
        while(M--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            a=findset(a),b=findset(b);
            if(a==b) {printf("-1\n");continue;}
            int x=pq[a].top();pq[a].pop();
            int y=pq[b].top();pq[b].pop();
            pq[a].push(x/2);pq[b].push(y/2);
            printf("%d\n",merge(a,b));
            fa[b]=a;
        }
    }
}