畅通工程

#include<stdio.h>
#include<algorithm>
#define N 101
using namespace std;
int Tree[N];
typedef struct Edge{
    int a,b;
    int cost;
}Edge;
int FindRoot(int x){
    if(Tree[x]==-1) return x;
    else{
        Tree[x]=FindRoot(Tree[x]);
        return Tree[x];
    }
}
bool cmp(Edge a,Edge b){
    return a.cost<b.cost;
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF&&n!=0){
        int i;
        Edge e[N];
        for(i=1;i<=m;i++)
            Tree[i]=-1;
        for(i=0;i<n;i++)
            scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].cost);
        sort(e,e+n,cmp);
        int a,b;
        int ans=0;
        for(i=0;i<n;i++){
            a=FindRoot(e[i].a);
            b=FindRoot(e[i].b);
            if(a!=b){
                Tree[b]=a;
                ans+=e[i].cost;
            }
        }
        int count=0;
        for(i=1;i<=m;i++)
            if(Tree[i]==-1)
                count++;
        if(count==1)
            printf("%d\n",ans);
        else
            puts("?");
    }
}

/*
*kruskal 最小生成树。并查集表征连通分量。
*/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4;
struct edge
{
    int u, v, w;
    edge(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
};
vector<edge> edges;
int father[maxn+5];
int n, m;

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

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

int getFather(int x)
{
    int a = x;
    while(x != father[x]) x = father[x];
    //路径压缩
    while(a != father[a])
    {
        int z = a; a = father[a]; father[z] = x;
    }
    return x;
}

void Create()
{
    int u, v, w, f;
    for(int i = 0;i < m; i++)
    {
        cin >> u >> v >> w;
        edges.push_back(edge(u, v, w));
    }
}

int Kruskal()
{
    Initial();
    sort(edges.begin(), edges.end(), cmp);
    int ans = 0, num = 0;
    for(int i = 0;i < edges.size(); i++)
    {
        int fu = getFather(edges[i].u);
        int fv = getFather(edges[i].v);
        if(fu != fv)
        {
            father[fu] = fv;
            ans += edges[i].w; num++;
            if(num == n-1) break;
        }
    }
    if(num != n-1) return -1;
    else return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> m >> n && m)
    {
        Create();
        int ans = Kruskal();
        if(ans == -1) cout << "?" << '\n';
        else cout << ans << '\n';
    }
    return 0;
}

#include<cstdio>
(802)#include<iostream>
#include<algorithm> 
using namespace std;
const int MAXN=100;
struct Edge{
	int from;
	int to;
	int len;
};
int father[MAXN];
int height[MAXN];
Edge e[MAXN*MAXN];
bool visit[MAXN]={false};
void initial(int n){
	for(int i=0;i<=n;i++){
		father[i]=i;         //初始每个结点的父亲为自己 
		height[i]=0;         //每个结点的高度初始为 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);          //x的根结点 
	y=find(y);          //找到 y 的根结点
	if(x!=y){           //x y 的根结点不一致
	   if(height[x]<height[y]){//矮树为高树的子树 
	   	father[x]=y;           //将 x树的根结点设为y 
	   }else if(height[x]>height[y]) father[y]=x;
	   else {          //两树一样高 
	        father[y]=x;
			height[x]++;      
	   }
	} 
	return ;
}
bool cmp(Edge x,Edge y){
	return x.len<y.len;
}
int kruskal(int m,int n){
	int sum=0,num=0;
	initial(m); //初始化  
	sort(e,e+n,cmp);
	for(int i=0;i<n;i++){
		Edge cur=e[i];
		if(find(cur.from)!=find(cur.to)&&visit[cur.from]==false&&visit[cur.to]==false){
			Union(cur.from,cur.to);//合并集合 
			visit[cur.from]==true;
			visit[cur.to]==true;
			sum+=cur.len;
		}
	}
	for(int i=1;i<=m;i++){
		if(i==find(i)) num++;
	}
	if(num==1) return sum;
	else return -1;
	
}

int main(){
    int n,m;//m个村庄，n条道路 
    while(scanf("%d",&n)!=EOF){
    	if(n==0) break;
    	scanf("%d",&m);           
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].len);  
        }
        int answer=kruskal(m,n);
        if(answer!=-1) printf("%d\n",answer);
        else printf("?\n");
    }
    return 0;
} 

只想问一下各位大佬，为什么我想着用DFS来遍历全部节点，得出每次的成本总和，

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

//自己回忆了下prim算法按感觉写的

//这道题实在想爆粗口，开始写觉得正确死活过不了，仔细查看样例，发现居然有 3 4 6，3 4 5 这样的毒数据，我真是***了，小改了一下过了

//望大家注意

int dis[105][105];

int Visited[105][105];

int visited[105];

int main(void){

    int n,m,i,j,point,res,k,minDis,start,end,cnt,temp;

    while(scanf("%d %d",&n,&m) != EOF){

        if(n == 0) return 0;

        memset(dis,0,sizeof(dis));

        memset(visited,0,sizeof(visited));

        memset(Visited,0,sizeof(Visited));

        for(i = 0;i < n;i++){

            scanf("%d %d",&j,&k);

            if(Visited[j][k] == 0 ){      //两个节点之间的距离取最小的那一个

                Visited[j][k] = Visited[k][j] = 1;

                scanf("%d",&dis[j][k]);

                dis[k][j] = dis[j][k];

            }

            else {

                scanf("%d",&temp);

                if(temp < dis[j][k]){

                    dis[j][k] = temp;

                    dis[k][j] = temp;

                }

            }

        }

        visited[1] = 1;

        point = m - 1;

        res = 0;

        while(point){

            minDis = 9999999;

            for(i = 1; i <= m;i++){

                if(visited[i] == 1){

                    for(j = 1;j <= m;j++){

                        if(visited[j] == 0 && dis[i][j] != 0){

                            if(dis[i][j] < minDis){

                                minDis = dis[i][j];

                                end = j;

                            }

                        }

                    }

                }

            }

            visited[end] = 1;

            res += minDis;

            point--;

        }

        cnt = 0;

        for(i = 1 ;i <= m ;i++){

            if(visited[i] == 1) cnt++;

        }

        if(cnt == m) printf("%d\n",res);

        else {

            printf("?\n");

        }

    }

    return 0;

}

#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;

int matrix[101][101];
int dist[101];

int main(){
    int i,j,n,m,x,y,cost;
    
    while(cin>>n>>m){
        if(n==0){break;}
        else{
            for(i=0;i<101;++i){
                for(j=0;j<101;++j){
                    if(i==j){matrix[i][j]=0;}
                    else{matrix[i][j]=INT_MAX;}
                }
            }
            for(i=0;i<n;++i){
                cin>>x>>y>>cost;
                if(matrix[x][y]>cost){matrix[x][y]=matrix[y][x]=cost;}//初始化
            }
            bool is_connect=true;
            int count=0;
            for(i=1;i<=m;++i){//判断是否连通
                count=0;
                for(j=1;j<=m;++j){
                    if(matrix[i][j]==INT_MAX){++count;}
                }
                if(count==m-1){is_connect=false;}//如果一个村除了到自己的距离都是INT_MAX,说明图不连通
            }
            if(is_connect==false){cout<<"?"<<endl;}
            else{//prim方法构造最小生成树
                int sum=0,count=1,min_dist,t;
                for(i=1;i<=m;++i){dist[i]=matrix[1][i];}
                while(count<m){
                    min_dist=INT_MAX;
                    for(i=1;i<=m;++i){
                        if(dist[i]<min_dist&&dist[i]!=0){min_dist=dist[i];t=i;}
                    }
                    dist[t]=0;
                    sum+=min_dist;
                    for(i=1;i<=m;++i){
                        if(matrix[t][i]<dist[i]){dist[i]=matrix[t][i];}
                    }
                    ++count;
                }
                cout<<sum<<endl;
            }
        }
    }
    
    
    return 0;
}

#include<stdio.h>
#include<algorithm>
using namespace std;
int tree[110];
struct Edge{
    int a,b;
    int cost;
}buf[110];
bool cmp(Edge a,Edge b){
    return a.cost<b.cost;
}
int sum[110];
int findroot(int x){
    if(tree[x]==-1){
        return x;
    }
    else {
        int tmp=findroot(tree[x]);
        tree[x]=tmp;
        return tmp;
    }
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0){
            break;
        }
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&buf[i].a,&buf[i].b,&buf[i].cost);
        }
        sort(buf+1,buf+1+n,cmp);
        for(int i=1;i<=m;i++){
            tree[i]=-1;
            sum[i]=1;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            int a=findroot(buf[i].a);
            int b=findroot(buf[i].b);
            if(a!=b){
                tree[a]=b;
                sum[b]=sum[a]+sum[b];
                ans=ans+buf[i].cost;
            }
        }
        int flag=0;
        for(int i=1;i<=m;i++){
            if(sum[i]==m){
                flag=1;
                break;
            }
        }
        if(flag!=0){
            printf("%d\n",ans);
        }
        else printf("?\n");
    }
    return 0;
}

def findRoot(village):
    global villages
    if villages[village] == -1:
        return village
    else:
        temp = findRoot(villages[village])
        villages[village] = temp
        return temp
while True:
    try:
        n,m = list(map(int,input().split()))
        if n == 0:
            break
        roads = []
        for i in range(n):
            roads.append(list(map(int,input().split())))
        values = 0
        villages = [-1 for i in range(m+1)]
        nodeNum = 1
        roads.sort(key=lambda x:x[2])
        for i in range(n):
            a = findRoot(roads[i][0])
            b = findRoot(roads[i][1])
            if a != b:
                villages[a] = b
                values += roads[i][2]
                nodeNum += 1
                if nodeNum == m:
                    break
        if nodeNum == m:
            print(values)
        else:
            print('?')
    except Exception:
        break

最小生成树
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

class Edge implements Comparable{
    int begin;
    int end;
    int cost;
    Edge next;
    public Edge(int begin, int end, int cost){
        this.begin = begin;
        this.end = end;
        this.cost = cost;
        this.next = null;
    }
    @Override
    public int compareTo(Object o){
        Edge edge = (Edge) o;
        return this.cost - edge.cost;
    }
}

public class Main{
    static int[] root;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            int N = scan.nextInt();
            int M = scan.nextInt();
            root = new int[M+1];
            for(int i=0;i<=M;i++)
                root[i] = -1;
            ArrayList<Edge> arr = new ArrayList<Edge>();
            for(int i=0;i<N;i++){
                Edge edge = new Edge(scan.nextInt(), scan.nextInt(), scan.nextInt());
                arr.add(edge);
            }
            Collections.sort(arr);
            int sum=0;
            while(!arr.isEmpty()){
                Edge tmp = arr.get(0);
                int a = findRoot(tmp.begin);
                int b = findRoot(tmp.end);
                if(a==b) arr.remove(0);
                else{
                    root[a] = b;
                    sum += tmp.cost;
                }
            }
            int cnt=0;
            for(int i=1;i<=M;i++)
                if(root[i]==-1) cnt++;
            if(cnt==1) System.out.println(sum);
            else System.out.println("?");
        }
    }
    
    public static int findRoot(int x){
        if(root[x]==-1) return x;
        int tmp = findRoot(root[x]);
        root[x] = tmp;
        return tmp;
    }
}

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

const int MAXN = 101;

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

vector<Edge>edge(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;  //结点的高度为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 m, int n) { //克鲁斯卡尔算法求最小生成树
    Initial(m);
    sort(edge.begin(), edge.begin() + n);   //边按权值排序
    int sum = 0,    //边权和（总长度）
        count = 0;  //边数
    for (int i = 0; i < n; i++) {
        Edge current = edge[i];
        if (Find(current.from) != Find(current.to)) {
            Union(current.from, current.to);
            sum += current.length;  //边权累加
            count++;    //统计边数
        }
    }
    //若边数太少不足以构成连通树（原图也一定不是连通图），则返回错误信息（-1）；
    //否则返回最小总长度（sum）
    return count == m - 1 ? sum : -1;
}

int main() {
    int n, m;
    while (cin >> n >> m && n) {
        for (int i = 0; i < n; i++) {
            cin >> edge[i].from >> edge[i].to >> edge[i].length;
        }
        int result = Kruskal(m, n);
        result == -1 ? cout << '?' << endl : cout << result << endl;
    }
    return 0;
}

//这道题算是比较常规的题了，采用kruskal算法并利用并查集思想求最小生成树
#include "stdio.h"
#include "queue"
using namespace std;
struct Edge{
    int villageS;//源端的村庄编号
    int villageT;//目的端的村庄编号
    int weight;
};
int N,M;//N为道路数目，M为村庄数目
priority_queue<Edge> myPQueue;
int Father[101];//并查集得根存储

bool operator < (Edge lhs,Edge rhs){
    return lhs.weight > rhs.weight;
}

void Init(){
    for (int i = 1; i <= M; ++i) {
        Father[i] = i;
    }
    while (!myPQueue.empty())
        myPQueue.pop();
}

int find(int x){
    if (Father[x] != x){
        Father[x] = find(Father[x]);
    }
    return Father[x];
}

int kruskal(){
    int sum = 0;//存储路径总长
    while (!myPQueue.empty()){
        Edge edge = myPQueue.top();
        myPQueue.pop();
        int villageS = edge.villageS,villageT = edge.villageT;
        if (find(villageS) != find(villageT)){
            Father[find(villageT)] = find(villageS);//Union操作
            sum += edge.weight;
        }
    }
    int count = 0;
    for (int i = 1; i <= M; ++i) {
        if (Father[i] == i)
            ++count;
    }
    if (count != 1)//有多个连通分支，无法形成最小生成树
        return -1;
    else
        return sum;
}

int main(){
    while (scanf("%d",&N)!=EOF){
        if (N == 0)
            break;
        scanf("%d",&M);
        Init();//对邻接矩阵和并查集进行初始化
        int villageS,villageT,weight;
        for (int i = 1; i <= N; ++i) {//道路入优先队列
            scanf("%d%d%d",&villageS,&villageT,&weight);
            Edge edge;edge.villageS = villageS;
            edge.villageT = villageT;edge.weight = weight;
            myPQueue.push(edge);
        }
        int sum = kruskal();
        if (sum != -1)
            printf("%d\n",sum);
        else
            printf("?\n");
    }
}