1076.txt

厦门大学OJ上的ACM题1076源码

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;   
}