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****************************************************/新聞熱點
疑難解答
