Think: 先构图，然后用最小生成树的方法解。。。 任然使用PRim算法
Problem Description 也许，人活着就是要尝试人世间的酸甜苦辣，喜怒哀乐，经历从婴儿到老人的一个过程吧！能看，能想，能爱，能恨，这就是活人与死人的区别。不要想着死后会怎样，谁也不知道。所以要好好的活着，宽待自己，好好珍惜身边的人！ 现在，上帝之手宽恕与你。把你人生中所要经历的所有的酸甜苦辣全部摆在你的面前。你一生需要经历n种事情。每种事情都有一个权值x。上帝给了你n-1个时光隧道。你可以把时光隧道放在任意两种事情的中间，如果你把时光隧道放在a,b中间，那么你需要花费3*(xa+xb)+7 。现在，你需要把这n-1个时光隧道连在n种事情中间，使得任意两种事情都会相连，并且花费最小。输出最小花费。 Input 首先输入一个数T，代表有T组数据。 接下来一行输入一个数n。 接下来的一行输入n个数，第i个数代表第i种事情的权值。 n<=1000,每种事情的权值<=100000； T<=60 Output 输出T行，每行输出最小花费。 Example Input
1 2 1 2
Example Output
16
#include<bits/stdc++.h>#define MAX 0x3f3f3f;using namespace std;int Map[1050][1050];int dis[1050];bool vis[1050];int Prim(int n);int main() { int T, d, n; int i, j; int ans; int a[1050]; cin >> T; while(T --) { memset(vis, false, sizeof(vis)); cin >> n; for (i = 0;i <= n;i ++) { for (j = 0;j <= n;j ++) { if (i == j) Map[i][j] = 0; else Map[i][j] = MAX; } } for (i = 1;i <= n;i ++) { cin >> a[i]; } for (i = 0;i <= n;i ++) { for (j = i + 1;j <= n;j ++) { d = 3 * (a[i] + a[j]) + 7; if (Map[i][j] > d) { Map[i][j] = Map[j][i] = d; } } } ans = Prim(n); cout << ans << endl; } return 0; } int Prim(int n) { int i, j, t; for (i = 1;i <= n;i ++) { for (j = 1;j <= n - 1;j ++) { dis[i] = Map[i][j]; } } vis[0] = true; int sum = 0; for (i = 1;i <= n;i ++) { t = i; int MIN = MAX; for (j = 1;j <= n;j ++) { if (vis[j] == false && dis[j] < MIN) { MIN = dis[j]; t = j; } } sum = sum + MIN; vis[t] = true; for (j = 1;j <= n;j ++) { if (vis[j] == false && dis[j] > Map[t][j]) dis[j] = Map[t][j]; } } return sum; }/***************************************************User name: Result: AcceptedTake time: 752msTake Memory: 2236KBSubmit time: 2017-02-20 15:59:46****************************************************/新闻热点
疑难解答
