xmu 1074: 安全网络 ver.1（MST模型）

1074: 安全网络 ver.1

题目描述

　　现在有个一个内部局域网络，里面有N台机器。为了某种安全原因的考虑，每两台机器之间的通讯都是经过加密的。由于不同机器之间传输的内容不同，所以他们通讯采用的加密级别也不大相同。不同的加密级别导致破解的难度不一样，越高的加密级别破解需要的时间也越多。如果我们获得了编号为i的机器的完全控制权，另外我们破解了机器i和机器j之间的加密信息，那么我们就得到了机器j的完全控制权。
　　现在你通过了某种手段入侵了1号机器，得到了这台机器的完全控制权，为了扩大劳动果实，你准备对其余的机器也在你的控制当中，但是由于需要破解加密信息才能控制其它机器，你又不想浪费太多时间在破解上，现在你来算算你至少需要多少时间才能完全控制整个网络。

输入

　　输入的第一行是一个正整数N(0 < N <= 100)，表示机器的数目。
　　输入的第二行开始到第N+1行，每行N个整数，第i+1行的第j个数字T_ij表示破解机器i和机器j之间的加密算法所需要的时间，范围在[0..100,000]之间。另外T_ij= T_ji，T_ii = 0。

输出

　　输出完全控制所有机器的最少时间。

样例输入

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

样例输出

28

提示

　　破解机器1和机器2、机器2和机器3、机器3和机器4之间的加密信息，即可完全控制所有机器。

来源

xmu

思路：完全的最小生成树模型。这题用prim算法比较好处理输入

代码：

#include<bits/stdc++.h>
#define maxn 110
#define INF 0x7fffffff
using namespace std;

int Map[maxn][maxn],dis[maxn],vis[maxn];
int N;

void prim(){//Prim的算法
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=N;i++) dis[i]=Map[1][i];
    vis[1]=1;int ans=0;
    for(int p=1;p<=N-1;p++){//注意只能循环Ｎ－１次
        int Min=INF,t;
        for(int i=1;i<=N;i++) if(!vis[i] && dis[i]<Min)
            Min=dis[t=i];
        ans+=Min;vis[t]=1;
        for(int i=1;i<=N;i++) if(!vis[i] && dis[i]>Map[i][t])
            dis[i]=Map[t][i];
    }
    printf("%d\n",ans);
}

int main(){
    //freopen("in.txt","r",stdin);
    while(cin>>N){
        for(int i=1;i<=N;i++) for(int j=1;j<=N;j++)
            scanf("%d",Map[i]+j);
        prim();
    }
    return 0;
}