C/C++数据结构——道路建设（最小生成树Prim）

随着如今社会的不断变化，交通问题也变得越来越重要，所以市长决定建设一些公路来方便各个城市之间的贸易和交易。虽然市长的想法很好，但是他也遇到了一般人也经常头疼的问题，那就是手头的经费有限……在规划过程中，设计师们已经预算出部分城市之间建设公路的经费需求。现在市长想知道，它能不能将他的m个城市在有限的经费内实现公路交通。如果可以的话，输出Yes，否则输出No（两个城市不一定要直接的公路相连，间接公路到达也可以。）

测试输入包含多条测试数据
每个测试数据的第1行分别给出可用的经费c(<1000000)，道路数目n(n<10000)，以及城市数目m(<100)。
接下来的n行给出建立公路的成本信息，每行给出三个整数，分别是相连的两个城市v1、v2(0

对每个测试用例，输出Yes或No。

输入

20 10 5

1 2 6

1 3 3

1 4 4

1 5 5

2 3 7

2 4 7

2 5 8

3 4 6

3 5 9

4 5 2

输出

Yes

输入

10 2 2

1 2 5

1 2 15

输出

Yes

两个城市之间可能存在多条线路

链接：https://ac.nowcoder.com/acm/problem/15108 来源：牛客网

#include
#define INF 1e7
int map[105][105];
void Prim(int m,int c)
{
    int dist[m+1];
    int flag[m+1];
    for(int i=1;i<=m;i++){
        dist[i]=INF;
        flag[i]=0;
        if(map[1][i]
            dist[i]=map[1][i];
        }
    }
    dist[1]=0;
    flag[1]=1;
    for(int i=1;i
        int minC=INF,k;
        for(int j=1;j<=m;j++){
            if(dist[j]
                minC=dist[j];
                k=j;
            }
        }
        flag[k]=1;
        for(int j=1;j<=m;j++){
            if(map[k][j]
                dist[j]=map[k][j];
            }
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        ans+=dist[i];
    }
    if(ans<=c)
        printf("Yesn",ans);
    else
        printf("Non",ans);
}
int main()
{
    int c,n,m,v1,v2,h;
    while(scanf("%d%d%d",&c,&n,&m)!=EOF){
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                map[i][j]=INF;
            }
        }
        for(int i=0;i
            scanf("%d%d%d",&v1,&v2,&h);
            if(map[v1][v2]==INF||(map[v1][v2]!=INF&&map[v1][v2]>h)){
                map[v1][v2]=h;
                map[v2][v1]=h;
            }
            
        }
        Prim(m,c);
    }
}

单纯的一个套Prim算法的模板题，弄懂算法原理其实很好理解，可以看看这篇文章，我大致讲了一下。https://blog.csdn.net/weixin_44546342/article/details/124926750?spm=1001.2014.3001.5501

Prim
可以使用堆优化，类似Dijkstra，但是使用堆优化，效率未必提高。
对于完全图的情况：
不使用堆优化，时间复杂度为O(n²)；
使用堆优化，时间复杂度为O(n²logn^)。
所以说对于以邻接矩阵输入的图，没必要去用Kruskal。
以上摘自牛客竞赛