还是畅通工程

#include <stdio.h>
#include <algorithm>
#define N 101
using namespace std;

int parent[N];
struct Edge{
    int a;
    int b;
    int d;
}E[N*N];

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

int FindRoot(int x)
{
    if(parent[x]==-1) return x;
    else
    {
        int ret=FindRoot(parent[x]);
        parent[x]=ret;
        return ret;
    }
}

int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        if(n<=0) break;
        for(int i=1; i<=n*(n-1)/2; i++)
        {
            scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].d);
        }
        for(int i=1; i<=n; i++) parent[i]=-1;
        int treeNum=n;
        int totalDist=0;
        sort(E+1, E+1+n*(n-1)/2, cmp);
        for(int i=1; i<=n*(n-1)/2; i++)
        {
            if(treeNum==1) break;//通了以后就收工
            int x, y;
            x=FindRoot(E[i].a);
            y=FindRoot(E[i].b);
            if(x!=y)
            {
                parent[x]=y;
                treeNum--;
                totalDist+=E[i].d;
            }
        }
        printf("%d\n", totalDist);
    }
    return 0;
}

#include <stdio.h>
#include <algorithm>
using namespace std;

struct E{
    int a;
    int b;
    int value;
}edge[5000];
bool cmp(E a,E b){
    return a.value<b.value;
}
int point[5000];
int findroot(int x){
    if(point[x]==-1) return x;
    else{
        int tmp=findroot(point[x]);
        point[x]=tmp;
        return tmp;
    }
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int m=(n*(n-1))/2;
        for(int i=1;i<=n;i++){
            point[i]=-1;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
        }
        sort(edge+1,edge+m+1,cmp);
        int sum=0;
        for(int i=1;i<=m;i++){
            int x=findroot(edge[i].a);
            int y=findroot(edge[i].b);
            if(x!=y){
                sum+=edge[i].value;
                if(x>y) point[x]=y;
                else point[y]=x;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

#include <stdio.h>

typedef struct Edge{
    int from,to,len;
}Edge;

Edge e[10000];
int dad[100],h[100];

void Initial(int n)
{
    for(int i=0;i<=n;i++)
    {
        dad[i]=i;
        h[i]=0;
    }    
}

int Find(int x)
{
    if(x!=dad[x])
        dad[x]=Find(dad[x]);
    return dad[x];
}

void Union(int x,int y)
{
    x = Find(x);
    y = Find(y);
    if(x!=y)
    {
        if(h[x]<h[y])    dad[x]=y;
        else if(h[x]>h[y])    dad[y]=x;
        else{
            dad[y]=x;
            h[x]++;
        }
    }
    return;
}

int cmp(const void *a,const void *b)
{
    return (*(Edge*)a).len-(*(Edge*)b).len;
}

int Kruskal(int n,int num)
{
    Initial(n);
    qsort(e,num,sizeof(e[0]),cmp);
    int sum = 0;
    for(int i=0;i<num;i++)
    {
        if(Find(e[i].from)!=Find(e[i].to))
        {
            Union(e[i].from, e[i].to);
            sum+=e[i].len;
        }
    }
    return sum;
}

int main()
{
    int n,m,ans,i;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        m=n*(n-1)/2;
        for(i=0;i<m;i++)
        {
            scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].len);
        }
        ans=Kruskal(n, m);
        printf("%d\n",ans);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
typedef struct _Edge
{
	int a, b, cost;
	bool operator<(const struct _Edge &e) const { return cost < e.cost;	}
}Edge;
int tree[100] = {-1};
int findroot(int x)
{
	if (-1 == tree[x]) return x;
	tree[x] = findroot(tree[x]);
	return tree[x];
}
int main()
{
	int n = 0;
	while (cin >> n && 0 != n)
	{
		int m = n * (n - 1) / 2, min_cost = 0; Edge eg[5000]; for (int i = 0; i <= n; ++i) tree[i] = -1;
		for (int i = 0; i < m; ++i) cin >> eg[i].a >> eg[i].b >> eg[i].cost; sort(eg, eg + m);
		for (int i = 0; i < m; ++i)
		{
			int a = findroot(eg[i].a), b = findroot(eg[i].b);
			if (a != b) { tree[b] = a; min_cost += eg[i].cost;}
		}
		cout << min_cost << endl;
	}
	return 0;
}

#最小生成树Python写法，Kruskal算法
#(把所有点集放在一颗树上就相当于全部点连通；从最小权值构建树开始)
def findRoot(x):         #找树根，如果起始树根为自己
    global tree
    if (tree[x] == -1):
        return x
    else:
        temp = findRoot(tree[x])    
        tree[x] = temp
        return temp

try:
    while True:
        num = int(input())
        if num == 0:
            break
        roadsList = []
        for i in range(num * (num - 1) // 2):
            roadsList.append(list(map(int, input().split())))
        roadsList.sort(key=lambda x: x[2])   #Python中list排序可以指定第几号元素排
        tree = [-1 for i in range(num + 1)]  #初始化树，起始树根都为自己
        result = 0
        for i in range(num * (num - 1) // 2): #循环每条路
            a = findRoot(roadsList[i][0])    #查找路的两端的树根
            b = findRoot(roadsList[i][1])
            if a!=b:                         #如果树根相等说明在同一颗树上
                result += roadsList[i][2]    #因为从最小权值开始，所以得到的是最小生成树
                tree[a] = b          
        print(result)
except Exception:
    pass

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct edge{
    int a,b,cost;
}road[5000];

int f[5000],M,T,s;

inline int cmp(struct edge x ,struct edge y)
{
    return x.cost<y.cost;
}

int finds(int x)
{
    if(x!=f[x])
        f[x] = finds(f[x]);
    return f[x];
}
int krus()
{
    int x,y,k=0;
    for(int i=1;i<=T;i++){
        x = finds(road[i].a);
        y = finds(road[i].b);
        if(x!=y){
            s+=road[i].cost;
            if(x>y)
                f[x] = y;
            else
                f[y] = x;
        }
    }
    return s;
}

int main()
{
    while(cin>>M&&M){
        s = 0;
        T = M*(M-1)/2;
        for(int i=1;i<=T;i++){
            f[i] = i;
            cin>>road[i].a>>road[i].b>>road[i].cost;
        }
        sort(road+1,road+T,cmp);
        s = krus();
        cout<<s<<endl;
    }
    return 0;
}

//纯C语言版
#include <stdio.h>
#include <stdlib.h>
int Tree[100]; //用来保存每个节点的最上层的父亲节点，起始的根节点的父亲节点为-1
int findRoot(int x){
    if(Tree[x]==-1) return x; //说明该点的父亲节点是自己，相当于是根节点
    else{
        int tmp=findRoot(Tree[x]);//递归寻找最早的父亲节点
        Tree[x]=tmp;
        return tmp;
    }
}
struct Edge{
    int a;
    int b;
    int cost;
}edge[6000];
typedef struct Edge Edge;
int cmp(const void *x,const void *y){
    return (*(Edge*)x).cost-(*(Edge*)y).cost; //这里用<会有问题
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF && n!=0){
        for(int i=1;i<=n*(n-1)/2;i++){
            scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);
        }
        qsort(edge+1,n*(n-1)/2,sizeof(Edge),cmp);//将路径按距离排序 每次优先取最短的路径
        for(int i=1;i<=n;i++){
            Tree[i]=-1;
        }
        int ans=0;
        for(int i=1;i<=n*(n-1)/2;i++){
            int a=findRoot(edge[i].a);
            int b=findRoot(edge[i].b);
            if(a!=b){ //如果该边的两个端点的根节点相同，说明形成了环，那么这条边舍弃
                Tree[a]=b;
                ans+=edge[i].cost;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

写了最小生成树的两种方法

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
struct edge
{
	int start, end, length;
	edge(int s, int e, int l) :start(s), end(e), length(l) {}
};
bool comp(edge e1, edge e2)//升序排序比较函数
{
	return e1.length < e2.length;
}
struct cmp//函数对象/仿函数，用于构建小根堆
{
	bool operator()(edge e1, edge e2)
	{
		return e1.length > e2.length;
	}
};
int find_root(map<int,int>& V, int x)//检查x所在集合的根
{
	int root = x, temp;
	while (V.find(root) != V.end() && V[root] != root)
		root = V[root];
	//路径压缩：将从 x 到 根 的路径上的节点都直接指向代表这个集合的根,压缩集合树的高度
	while (V.find(x) != V.end() && V[x] != x)
	{
		temp = V[x];
		V[x] = root;
		x = temp;
	}
	return root;
}
int kruskal(vector<edge>& E, int n)//最小生成树 克鲁斯卡尔算法O(ElogE)
{
	int sum = 0, count = 0;//边权值和，边的条数

	map<int, int> V;//顶点集/并查集

	vector<edge>::iterator it = E.begin();
	while (count != n - 1)//n个顶点的树n-1条边
	{
		while (it != E.end())//边已经排序了
		{
			int a = find_root(V, it->start);
			int b = find_root(V, it->end);
			if (a != b)//不在集合中，即没有构成回路
			{
				V[b] = a;//并入集合
				sum += it->length;
				it++;
				break;
			}
			else
				it++;
		}
		count++;
	}
	return sum;
}

int prim(vector<edge>* E, int n)//堆优化的普利姆算法O(ElogV)
{
	int sum = 0, count = 0;
	vector<edge>::iterator it;
	map<int, int> V;
	V[1] = 1;//第一个节点放入顶点集中

	priority_queue<edge, vector<edge>, cmp> PQ;//优先队列/小根堆
	it = E[1].begin();
	while (it != E[1].end())//将第一个节点上的边放入堆
	{
		PQ.push(*it);
		it++;
	}
	while (count != n - 1)
	{
		while (!PQ.empty())
		{
			edge temp = PQ.top();
			int a = find_root(V, temp.start);
			int b = find_root(V, temp.end);
			if (a != b)//不构成回路
			{
				V[b] = a;//并入集合
				sum += temp.length;
				PQ.pop();
				//将以此边终点为起点的边纳入堆
				it = E[temp.end].begin();
				while (it != E[temp.end].end())
				{
					PQ.push(*it);
					it++;
				}
				break;
			}
			else
				PQ.pop();
		}
		count++;
	}
	
	return sum;
}
void test1()
{
	int n;
	vector<edge> E;//边集，kruskal算法用到边，还要排序，适合边集
	while (cin >> n && n != 0)
	{
		int num_edge = n * (n - 1) / 2;
		for (int i = 0; i < num_edge; i++)
		{
			int s, e, l;
			cin >> s >> e >> l;
			E.push_back(edge(s, e, l));
			E.push_back(edge(e, s, l));//本题输入是单向的，为了无向图prim算法增加反向边
		}
		sort(E.begin(), E.end(), comp);
		cout << kruskal(E, n) << endl;

		E.clear();
	}
}
void test2()
{
	int n;
	while (cin>>n && n != 0)
	{	
		int num_edge = n * (n - 1) / 2;
		vector<edge>* E = new vector<edge>[n + 1];//vector数组模拟邻接表
		for (int i = 0; i < num_edge; i++)
		{
			int s, e, l;
			cin >> s >> e >> l;
			E[s].push_back(edge(s, e, l));
			E[e].push_back(edge(e, s, l));
		}
		cout << prim(E, n) << endl;
	}
}
int main()
{
	//test1();
	test2();
	return 0;
}

#include<iostream>
(720)#include<bits/stdc++.h>

using namespace std;
struct Edge{
	int from;
	int to;
	int cost;
	bool operator<(const Edge& e) const{
		return cost<e.cost;
	}
}; 
Edge e[101];
int height[101];
int father[101];
int find(int x){
	if(father[x]!=-1) find(father[x]);
	else return x;
}

/*两条道路相互不可达，则连接，选取此道路。若已可达，则不能添加此道路，否则成环*/
bool union_node(int m,int n){
	int x=find(m);
	int y=find(n);
	if(x==y) return false;
	else{
		if(height[x]<height[y]) father[x]=y;
		else if(height[x]>height[y]) father[y]=x;
		else{
			father[x]=y;
			height[y]++;
		}
	}	
	return true;
}

int kruskal(int num){
	int ans = 0;
	sort(e,e + num);
	for(int i = 0 ; i < num ; i++){
		int x=e[i].from;
		int y=e[i].to;
		if(union_node(x,y)) ans+=e[i].cost;
	}
	return ans;
}
int main(){
	int n;
	while(cin>>n){
		memset(father,-1,sizeof(father));
		memset(height,0,sizeof(height));
		int num=(n-1)*n/2;
		for(int i=0;i<num;i++){
			cin>>e[i].from>>e[i].to>>e[i].cost;
		}
		cout<<kruskal(num)<<endl;
	}
}

#include <iostream>
#include<algorithm>
using namespace std;
int p[101];

struct edge{
int a;
int b;
int len;
}e[5000];
bool cmp(edge a,edge b){
   return a.len<b.len;
}
void inital(int n){
    for(int i=1;i<=n;i++){
        p[i]=i;
       
    }
}
int find(int x){
    if(p[x]!=x){
        p[x]=find(p[x]);
    }
    return p[x];
}
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y)   p[x]=y;
}
int kruskal(int n){
    inital(n);
    int ans=0;
    sort(e,e+n*(n-1)/2,cmp);
    for(int i=0;i<n*(n-1)/2;i++){
        int x=e[i].a,y=e[i].b;
       if(find(x)!=find(y)){
        unite(x,y);
        ans+=e[i].len;
       }
    }
    return ans;
}
int main() {
    int n;
    while(cin>>n){
        if(n==0)break;
      int m=n*(n-1)/2;
      for(int i=0;i<m;i++){
        cin>>e[i].a>>e[i].b>>e[i].len;
      }
      cout<<kruskal(n)<<endl;
    }
}

#include <cstdio>
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int father[10001];
void InitSet(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}
int FindFather(int u) {
    if (u == father[u]) {
        return u;
    } else {
        father[u] = FindFather(father[u]);
        return father[u];
    }
}
void UnionSet(int r, int t) {
    r = FindFather(r);
    t = FindFather(t);
    father[r] = t;
}
struct edge {
    int u;//边的两个结点、权值
    int v;
    int w;
    edge(int _u, int _v, int _w) {
        u = _u;
        v = _v;
        w = _w;
    }
};
bool cmp(edge a,edge b){
    return a.w<b.w;//从小到大最小生成树
}
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector<edge> edgev;//存储边的向量
        if(0==n){
            break;
        }
        for(int i=0;i<(n-1)*n/2;i++){
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            edge e(u,v,w);
            edgev.push_back(e);
        }
        InitSet(10001);
        sort(edgev.begin(),edgev.end(),cmp);
        int edgenum=0,totaledgesum=0;//边的数量与权值之和
        for(int i=0;i<edgev.size();i++){
            int u=edgev[i].u,v=edgev[i].v,w=edgev[i].w;
            if(FindFather(u)!=FindFather(v)){
                edgenum++;
                UnionSet(u,v);
                totaledgesum+=w;
                if(edgenum==n-1){ //最小树已经生成完毕
                    break;
                }
            }
        }
        printf("%d\n",totaledgesum);

    }
}
// 64 位输出请用 printf("%lld")

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

struct Point{
    int x;
    int y;
};
struct Edge{
    int from;
    int to;
    int length;
};

struct Point point[100];
struct Edge edge[100*99/2];
int father[100];
int heigth[100];
void initial(int n){
    int i;
    for (i = 0; i < n; i++){
        father[i] = i;
        heigth[i] = 0;
    }
        
}

int Find(int i){

        if (i != father[i]){
            father[i] = Find(father[i]);
        }
    
    return father[i];
}

void Uion(int a, int b){
    a = Find(a);
    b = Find(b);
    if (a != b){
        if (heigth[a] < heigth[b]){
            father[a] = b;
        }
        else if (heigth[a] > heigth[b])
        {
            father[b] = a;
        }
        else{
            father[b] =a;
            heigth[a]++;
        }
        
    }
}

int cmp(const void *a, const void *b){
    const struct Edge*edga = (const struct Edge*)a;
    const struct Edge*edgb = (const struct Edge*)b;
    if(edga->length < edgb->length) return -1;
    if (edga->length > edgb->length) return 1;
    return 0;
    
}
int kruskal(int n, int edgenum){
    initial(n);
    int ans = 0;
    qsort(edge, edgenum, sizeof(struct Edge), cmp);
    for (int i = 0; i < edgenum; i++){
        if (Find(edge[i].from) != Find(edge[i].to)){
            Uion(edge[i].from, edge[i].to);
                ans += edge[i].length;
        }
    }
    return ans;

}



int main(){
    int n, res;
    int a[100];
    while(scanf("%d", &n) != EOF){
        if (n == 0) break;
        for(int i = 0; i < n*(n-1)/2; i++){
            scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].length);
        }
        res = kruskal(n, n*(n-1)/2);
        printf("%d\n", res);
    }
    return 0;
}

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;

const int MAX=100;

int father[MAX];
int height[MAX];


struct Edge{
	int from;
	int to;
	int length;
};

Edge edge[MAX*MAX];

void Initial(int n){
	for(int i=0;i<=n;i++){
		father[i]=i;
		height[i]=0;
	}
}

int Find(int x){
	if(x!=father[x]){
		father[x]=Find(father[x]);
	}
	return father[x];
}

void Union(int x,int y){
	x=Find(x);
	y=Find(y);
	if(x!=y){
		if(height[x]<height[y]){
			father[x]=y;
		}else if(height[y]<height[x]){
			father[y]=x;
		}else{
			father[y]=x;
			height[x]++;
		}
	}
	return ;
}
bool cmp(Edge edge1,Edge edge2){
	return edge1.length<edge2.length;
}

int Kruskal(int n,int edgeNumber){
	Initial(n);
	sort(edge,edge+edgeNumber,cmp);
	int sum=0;
	for(int i=0;i<=edgeNumber;i++){
		Edge current=edge[i];
		if(Find(current.from)!=Find(current.to)){
			Union(current.from,current.to);
			sum+=current.length;
		}
	}
	return sum;
}

int main(){
	int n;
	while(cin>>n){
		if(n==0) break;
		int edgeNumber=(n-1)*n/2;
		Initial(n);
		for(int i=0;i<edgeNumber;i++){
			cin>>edge[i].from>>edge[i].to>>edge[i].length;
		}
		int sum=Kruskal(n,edgeNumber);
		cout<<sum<<endl;
	} 
}