注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu 1074.安全网络 ver.1  

2011-12-03 19:11:33|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1074.安全网络 ver.1
Time Limit: 1000 MS         Memory Limit: 65536 K
Total Submissions: 1359 (472 users)         Accepted: 697 (444 users)
[ My Solution ]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

28

Hint

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

Source
xmu
 
求最小生成树,用了下下模版额。。。
#include <cstdio>
#include <iostream>
#define inf 0x3fffffff
using namespace std;
#define MAXN 101
typedef int elem_t;
elem_t prim(int n,elem_t mat[][MAXN])
{
 elem_t min[MAXN],ret=0;
 int pre[MAXN];
 int v[MAXN],i,j,k;
 for (i=0;i<n;i++)
  min[i]=inf,v[i]=0,pre[i]=-1;
 for (min[j=0]=0;j<n;j++){
  for (k=-1,i=0;i<n;i++)
   if (!v[i]&&(k==-1||min[i]<min[k]))
    k=i;
  for (v[k]=1,ret+=min[k],i=0;i<n;i++)
   if (!v[i]&&mat[k][i]<min[i])
    min[i]=mat[pre[i]=k][i];
 }
 return ret;
}
int main()
{
    int i, j, n;
    int a[101][101];
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
    printf("%d\n", prim(n, a));
    return 0;
}
 
  评论这张
 
阅读(194)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017