畅通工程

#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 <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, m; //道路数、村庄数
    while (scanf("%d%d", &n, &m) != EOF) {
        vector<edge> edgev;//存储边的向量
        if (0 == n) {
            break;
        }
        if (n < m - 1) {
            printf("?\n"); //如果道路总数已经村庄数那么必定不连通直接break
            break;
        }
        for (int i = 0; i <n; 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;
            }
        }
        if (edgenum < m - 1) {
            printf("?\n"); //不连通
        } else {
            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 cost;
};
int father[101];
struct Edge edge[101];
int height[101];
void inital(int n){
    for(int i = 1; i <= n; i++){
        father[i] = i;
        height[i] = 1;
        
    }
}

int cmp(const void*a, const void*b ){
    struct Edge* edgea = (struct Edge *) a;
    struct Edge* edgeb = (struct Edge *) b;
    if(edgea->cost < edgeb->cost) return -1;
    else if(edgea->cost > edgeb->cost) return 1;
    return 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[y] > height[x])
            father[x] = y;
        else {
            father[y] = x;
            height[x]++;
        }
    }
}

int kruskal(struct Edge edge[], int edgenum){
    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)){
                Union(edge[i].from, edge[i].to);
                ans += edge[i].cost;
        
        
        }
    }
    return ans;
}

int main(){
    int n, m, a, b, c, res, x, y;
    while(scanf("%d %d", &n, &m)!=EOF){
        if (n == 0) break;
        inital(m);
        for(int i = 0; i < n; i++){
            scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].cost);
            
        }
        res = kruskal(edge, n);
        x = father[1];

        int tag = 0;
        for(int i = 2; i <= m; i++){
            y = Find(i);
            if (x != y) {
                tag = 1;
                
                break;
            }
                
                
               
        }
        if(tag == 0)
            printf("%d\n",res);
        else
            printf("%s\n", "?");
    }
  
    return 0;
}