1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 |
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 101;
- int a[MAXN][MAXN];
- int dis[MAXN];//每个点到源点的距离
- int book[MAXN];//每个点是否加入到最小生成树中
- int n;
- int Prim(){
- for(int i = 1; i <= n; i++){
- dis[i] = INT_MAX;
- }
- for(int i = 1; i <= n; i++){
- book[i] = 0;
- }
- dis[1] = 0;
- book[1] = 1;
- for(int i = 1; i < n; i++){
- int u=1, MIN = INT_MAX;//寻找离最小生成树距离最短的点
- for(int j = 2; j <= n; j++){
- if(book[j] == 0 && dis[j] < MIN){
- MIN = dis[j];
- u = j;
- }
- }
- book[u] = 1;
- for(int j = 1; j <= n; j++){
- if(book[j] == 0 && dis[j] > a[u][j]){
- dis[j] = a[u][j];
- }
- }
- }
- int sum = accumulate(dis+1, dis+n+1,0);
- return sum;
- }
- int main(){
- // ifstream cin("input.txt");
- // ofstream cout("output.txt");
- while(cin >> n ){
- if(n == 0)break;
- for(int i = 1; i <= n; i++){
- for(int j = 1; j <= n; j++){
- a[i][j] = 0;
- }
- }
- for(int i = 1; i <= n * ( n - 1) / 2; i++){
- int x, y, z;
- cin >> x >> y >> z;
- a[x][y] = a[y][x] = z;
- }
- int sum = Prim();
- cout << sum << endl;
- }
- }
|