首页 > 代码库 > SDUT OJ 之 人活着系列之寻找最完美的人生
SDUT OJ 之 人活着系列之寻找最完美的人生
人活着系列之寻找最完美的人生
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
也许，人活着就是要尝试人世间的酸甜苦辣，喜怒哀乐，经历从婴儿到老人的一个过程吧！能看，能想，能爱，能恨，这就是活人与死人的区别。不要想着死后会怎样，谁也不知道。所以要好好的活着，宽待自己，好好珍惜身边的人！
现在，上帝之手宽恕与你。把你人生中所要经历的所有的酸甜苦辣全部摆在你的面前。你一生需要经历n种事情。每种事情都有一个权值x。上帝给了你 n-1个时光隧道。你可以把时光隧道放在任意两种事情的中间，如果你把时光隧道放在a,b中间，那么你需要花费3*(xa+xb)+7 。现在，你需要把这n-1个时光隧道连在n种事情中间，使得任意两种事情都会相连，并且花费最小。输出最小花费。
输入
首先输入一个数T，代表有T组数据。
接下来一行输入一个数n。
接下来的一行输入n个数，第i个数代表第i种事情的权值。
n<=1000,每种事情的权值<=100000；
T<=60
输出
输出T行，每行输出最小花费。
示例输入
121 2
示例输出
16
算法：构造图，最小生成树
#include <iostream>#include <stdio.h>#include <string.h>#include <string>#include <algorithm>using namespace std;int a[1000];int map[1000][1000];int vis[1000];int dis[1000];void prim(int n){ int i, j; int sum=0; memset(vis, 0, sizeof(vis)); for(i=0; i<n; i++) { dis[i] = map[0][i] ; } vis[0]=1; int pos; for(i=1; i<n; i++) { int min=100000000; for(j=0; j<n; j++) { if(dis[j]<min && vis[j]==0) { min = dis[j]; pos = j; } } vis[pos]=1; sum =sum+min; for(j=0; j<n; j++) { if(vis[j]==0 && map[pos][j]<dis[j] ) dis[j] = map[pos][j] ; } } printf("%d\n", sum );}int main(){ int t, i, j, n; int dd; cin>>t; while(t--) { cin>>n; for(i=0; i<n; i++) { cin>>a[i] ; } for(i=0; i<n; i++) { for(j=i+1; j<n; j++) { dd = 3*(a[i]+a[j])+7 ; map[i][j] = dd; map[j][i] = dd; } } prim(n) ; } return 0;}
SDUT OJ 之 人活着系列之寻找最完美的人生
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。