Hdu1233

#include<bits/stdc++.h>
using namespace std;

const int maxn=100;
int n,m;
int ans=0;

typedef struct
{
    int lowcost;
    int adjvex;
    //例如：shortEdge[2].adjvex=4，意思就是，当前这个点2与点4最近。
    //shortEdge[2].lowcost=6，意思是点2与当前最近点4直接的距离为6
}Element;

void Prim(int arc[maxn][maxn],int w)
{
    int i,j,k;
    int Min;
    Element shortEdge[n+1];
    for(i=1;i <= n;i++)
    {
        shortEdge[i].lowcost=arc[w][i];
        shortEdge[i].adjvex=w;
    }
    shortEdge[w].lowcost=0;
    for(i=1;i <= n-1;i++)//寻找最近点
    {
        Min=0x3f3f3f3f;
        for(j=1;j <= n;j++)
        {
            if((shortEdge[j].lowcost!=0)&&(shortEdge[j].lowcost < Min))//1.该点是否已经加入最小生成树的集合里；2.该点是否小于Min(即寻找最小距离的)
            {
                Min=shortEdge[j].lowcost;
                k=j;
            }
        }
        ans+=shortEdge[k].lowcost;
        shortEdge[k].lowcost=0;//将k的最小花费设置为0，这里相当于一个集（最小生成树中的点的集合U），也可以用一个数组来实现
        for(j=1;j<= n;j++)//更新操作
        {
            if(arc[k][j]< shortEdge[j].lowcost)
            {
                shortEdge[j].lowcost=arc[k][j];
                shortEdge[j].adjvex=k;
            }
        }
    }
}

int main()
{
    int arc[maxn][maxn];
    int a,b,c;
    //万事开头难，初始化时需根据题目的要求进行初始化
    while(cin>>n&&n)
    {
        ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)arc[i][j]=0;
                else arc[i][j]=0x3f3f3f3f;
            }
        }
        m=n*(n-1)/2;

        for(int i=0;i<m;i++)
        {
            cin>>a>>b>>c;
            if(arc[a][b]>c)
            {
                arc[a][b]=c;
                arc[b][a]=c;
            }

        }
        Prim(arc,1);
        cout<<ans<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st,false,sizeof st);
    int res = 0;
    for (int i = 0; i < n; i ++ )//这里是逆向的求最小生成树，如果有些题目要求从第一个节点开始，则可以把循环修改一下，这里的i=0的时候，就是进行初始化
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            //!st[j]表示的是这个点没有被用过
            //(t == -1 || dist[t] > dist[j])代表的是要么是第一次开始找（也就是t == -1，此时不存在dist[t] > dist[j]）的情况，要么找到了一个点j，集合到点j的距离小于到t的距离，就更新t
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}


int main()
{
    while(cin>>n&&n)
    {
        if(n==0)break;
        memset(g, 0x3f, sizeof g);
        m=n*(n-1)/2;
        while (m -- )
        {
            int a, b, c;
            cin>>a>>b>>c;
            g[a][b] = g[b][a] = min(g[a][b], c);
        }
        int t = prim();
        cout<<t<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int NUM=103;
int S[NUM];//并查集
struct Edge{//定义边
    int u,v,w;
}edge[NUM*NUM];

bool cmp(Edge a,Edge b){return a.w<b.w;}

int find(int u){return S[u]==u?u:find(S[u]);}//查询并查集，返回u的根节点

int n,m;

int kruskal()
{
    int ans=0;
    for(int i=1;i<=n;i++)S[i]=i;//初始化，开始时每个村庄都是单独的集
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        int b=find(edge[i].u);//边的前端点u属于哪个集
        int c=find(edge[i].v);//边的后端点v属于哪个集
        if(b==c)continue;//产生圈，丢弃这个边
        S[c]=b;//合并
        ans+=edge[i].w;//计算MST
    }
    return ans;
}

int main()
{
    while(cin>>n&&n)
    {
        m=n*(n-1)/2;
        for(int i=1;i<=m;i++)
        {
            cin>>edge[i].u>>edge[i].v>>edge[i].w;
        }
        cout<<kruskal()<<endl;
    }
    return 0;
}