还是畅通工程

#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<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;
	} 
}

为什么Prime算法过不了呢

import java.util.ArrayList;

import java.util.Arrays;

import java.util.LinkedList;

import java.util.Scanner;

class Edge{

    int v1;

    int v2;

    int cost;

    public Edge(int v1, int v2, int cost) {

        this.v1 = v1;

        this.v2 = v2;

        this.cost = cost;

    }

}

class ListNode{

    public int v;

    public int cost;

    ListNode next;

    public ListNode(int v, int cost) {

        this.v = v;

        this.cost = cost;

    }

    public ListNode() {

    }

}

class Graph{

    ListNode[] graph;

    int size;

    public Graph(int size,Edge[] edges) {

        this.size = size;

        graph=new ListNode[size+1];

        Arrays.fill(graph,new ListNode());

        for (Edge e:edges)

        {

            ListNode n1 = new ListNode(e.v1, e.cost);

            ListNode n2 = new ListNode(e.v2, e.cost);

            n2.next=graph[e.v1].next;

            graph[e.v1].next=n2;

            n1.next=graph[e.v2].next;

            graph[e.v2].next=n1;

        }

    }

    public int prime(int start)

    {

        int []cost=new int[size+1];

        int []visited=new int[size+1];

        Arrays.fill(cost,Integer.MAX_VALUE);

        Arrays.fill(visited,0);

        cost[start]=0;

        visited[start]=1;

        for (ListNode p=graph[start].next;p!=null;p=p.next)

        {

            cost[p.v]=p.cost;

        }

        int sumCost=0;

        for (int i = 1; i < size; i++) {

            int minIndex=-1;

            int minCost=Integer.MAX_VALUE;

            for (int j = 1; j < size+1; j++) {

                if (visited[j]==0 && cost[j]<minCost)

                {

                    minCost=cost[j];

                    minIndex=j;

                }

            }

            visited[minIndex]=1;

            sumCost+=minCost;

            ListNode node = graph[minIndex].next;

            while (node!=null)

            {

                if (visited[node.v]==0 && cost[node.v]>node.cost)

                {

                    cost[node.v]=node.cost;

                }

                node=node.next;

            }

        }

        return sumCost;

    }

}

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext())

        {

            int size = scanner.nextInt();

            if (size==0)

                break;

            Edge[] edges = new Edge[size * (size - 1) / 2];

            for (int i = 0; i < size*(size-1)/2; i++) {

                int v1 = scanner.nextInt();

                int v2 = scanner.nextInt();

                int cost = scanner.nextInt();

                edges[i]=new Edge(v1,v2,cost);

            }

            Graph g = new Graph(size,edges);

            System.out.println(g.prime(1));

        }

    }

}

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100;
struct Edge{
    int from;
    int to;
    int length;
};
Edge edge[MAXN * MAXN]; //最多不超MAXN的平方个边
int father[MAXN];
int height[MAXN];
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[y] = x;
        } else if(height[x] < height[y]){
            father[x] = y;
        } else{
            father[x] = y;
            height[y]++;
        }
    }
    return;
}
bool cmp(Edge x, Edge y){
    return x.length <y.length;
}
int Kruskal(int EdgeNum){
    int sum=0;
    sort(edge, edge+EdgeNum, cmp);  //从最小边开始选
    for(int i=0; i<EdgeNum; ++i){
        int from = Find(edge[i].from);
        int to = Find(edge[i].to);
        if(from != to){
            Union(from, to);
            sum += edge[i].length;
        }
    }
    return sum;
}
int main(){
    int n;
    while (cin >> n && n!=0){
        Initial(n);
        int cnt = n*(n-1)/2;
        for(int i=0; i<cnt; ++i){
            cin >> edge[i].from >> edge[i].to >> edge[i].length;
        }
        cout << Kruskal(cnt) << endl;
    }
}

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

const int MAXN = 100;

struct Edge {
    int from;   //边的起点
    int to;     //边的终点
    int length; //边的长度
    bool operator<(const Edge& e)const {    //重载小于号
        return length < e.length;
    }
};

vector<Edge>edge(MAXN* MAXN);   //边集
vector<int>father(MAXN);        //父亲结点
vector<int>height(MAXN);        //结点高度

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]++;
        }
    }
}

int Kruskal(int n, int edgeNum) {   //最小生成树的克鲁斯卡尔算法
    Initial(n);
    sort(edge.begin(), edge.begin() + edgeNum); //边按权值（长度）排序
    int sum = 0;
    for (int i = 0; i < edgeNum; 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 && n != 0) {
        Initial(n);
        int edgeNum = n * (n - 1) / 2;
        for (int i = 0; i < edgeNum; i++) {
            cin >> edge[i].from >> edge[i].to >> edge[i].length;
        }
        int answer = Kruskal(n, edgeNum);
        cout << answer << endl;
    }
    return 0;
}