1076.安全網絡 ver.3
Time Limit: 5000 MS         Memory Limit: 65536 K 
Total Submissions: 981 (129 users)         Accepted: 220 (92 users) 
[ My Solution ] 

Description
　　現在有個一個內部局域網絡，里面有N臺機器。為了某種安全原因的考慮，有些機器之間是無法直接通訊的，即使可以通訊，機器與機器之間的通訊都是經過加密的。由于不同機器之間傳輸的內容不同，所以他們通訊采用的加密級別也不大相同。不同的加密級別導致破解的難度不一樣，越高的加密級別破解需要的時間也越多。如果我們獲得了編號為i的機器的完全控制權，且機器i和機器j可以直接通訊，另外我們破解了機器i和機器j之間的加密信息，那么我們就得到了機器j的完全控制權。
　　現在你通過了某種手段入侵了1號機器，得到了這臺機器的完全控制權，為了擴大勞動果實，你準備對其余的機器也在你的控制當中，但是由于需要破解加密信息才能控制其它機器，你又不想浪費太多時間在破解上，現在你來算算你至少需要多少時間才能完全控制整個網絡。



Input
　　輸入的第一行是兩個正整數N(2 <= N <= 100,000) M(0 < M <= 200,000)，表示機器的數目和允許通訊的機器對數。
　　輸入的第二行開始到第M+1行，每行3個整數，A B T( 1 <= A, B <= N, T <= 10,000, A ≠ B)，表示機器A和機器B之間可以互相通訊，且破解這個通訊的時間是T。輸入保證不存在重復的AB對。



Output
　　輸出完全控制所有機器的最少時間。如果無法滿足要求則輸出-1。



Sample Input
4 4
1 2 4
1 3 9
2 3 2
4 3 1



Sample Output
7



RunId 29718 of Problem 1076
Submit Time: 2008-11-02 19:08:05    Language: G++    Code Length: 1981 B 
    Result: Accepted    Time: 780 MS    Memory: 7620 K    Judge: Apple





#include <stdio.h>   
#include <stdlib.h>   
typedef struct arcnode{   
    long adjvex;   
    long info;   
    arcnode *nextarc;   
}arcnode;   
arcnode *graph[100001];   
long hsort[100001];   
long hpos[100001];   
long curnum = 0;   
long closedge[100001] = {0};   
void heapadjust(long pos)   
{   
    for (long i=pos/2; i>=1; i/=2){   
        long key = hsort[i];   
        long s = i;   
        for (long j=s*2; j<=curnum; j*=2){   
            if (j+1<=curnum && closedge[hsort[j+1]]<closedge[hsort[j]])   
                j++;   
            if (closedge[key] < closedge[hsort[j]])   
                break;   
            hsort[s] = hsort[j];   
            hpos[hsort[s]] = s;   
            s = j;   
        }   
        hsort[s] = key;   
        hpos[key] = s;   
    }   
}   
int main()   
{   
    long n, m;   
    scanf("%ld %ld", &n, &m);   
    for (long j=1; j<=n; j++)   
        graph[j] = NULL;   
    for (long i=1; i<=m; i++){   
        arcnode *p = (arcnode *)malloc(sizeof(arcnode));   
        long vex;   
        scanf("%ld %ld %ld", &vex, &p->adjvex, &p->info);   
        p->nextarc = graph[vex];   
        graph[vex] = p;   
        arcnode *r = (arcnode *)malloc(sizeof(arcnode));   
        r->adjvex = vex;   
        r->nextarc = graph[p->adjvex];   
        graph[p->adjvex] = r;   
        r->info = p->info;   
    }   
    long time = 0;   
    arcnode *p=graph[1];   
    while (p != NULL){   
        closedge[p->adjvex] = p->info;   
        hsort[++curnum] = p->adjvex;   
        hpos[p->adjvex] = curnum;   
        p = p->nextarc;   
        heapadjust(curnum);   
    }   
    closedge[1] = -1;   
    bool complete = 1;   
    for (long k=2; k<=n; k++){   
        long pos = 0;   
        if (curnum >= 1){   
            pos = hsort[1];   
            hsort[1] = hsort[curnum--];   
            hpos[hsort[1]] = 1;   
            heapadjust(2);   
        }   
        if (pos==0){   
            complete = 0;   
            break;   
        }   
        time += closedge[pos];   
        closedge[pos] = -1;   
        for (arcnode *q=graph[pos]; q!=NULL; q=q->nextarc)   
            if (closedge[q->adjvex]>q->info || closedge[q->adjvex]==0){   
                if (closedge[q->adjvex] == 0){   
                    hsort[++curnum] = q->adjvex;   
                    hpos[q->adjvex] = curnum;   
                }   
                closedge[q->adjvex] = q->info;   
                heapadjust(hpos[q->adjvex]);   
            }   
    }   
    if (complete == 1)   
        printf("%ld", time);   
    else  
        printf("-1");   
    return 0;   
}