继续畅通工程-题解（C++代码）

287 阅读 2 评论 0 点赞

克鲁斯卡尔算法，把状态为1的首先初始到k中，然后对状态为0的边进行从小到大排序，依次加入到k中，看是否形成环，形成环跳过就可以了
```cpp
#include <iostream>
#include<stack>
using namespace std;
typedef struct edge{//定义一条边
    int start;//定义开始节点
    int end;//定义结束节点
    int weight;//定义这条边的权值
    int state;//定义修建状态
};
int zhixing(edge *e,int low,int high){
    int i=low;
    int j=high;
    edge key=e[i];
    while(i<j){
        while(i<j&&e[j].weight>=key.weight){
            j--;
        }
        if(i<j){
            e[i++]=e[j];
        }
        while(i<j&&e[i].weight<=key.weight){
            i++;
        }
        if(i<j){
            e[j--]=e[i];
        }
    }
    e[i]=key;
    return i;
}
void kp(edge *e,int low,int high){
    if(low<high){
        int key=zhixing(e,low,high);
        kp(e,low,key-1);
        kp(e,key+1,high);
    }
}
bool tuopu(int **p,int n){//有环，返回true
    int k[n];
    for(int i=0;i<n;i++){
        k[i]=0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(p[i][j]!=0){
                k[i]++;
            }
        }
    }
    stack<int> s;
    //将k中<=1的存到栈中
    for(int i=0;i<n;i++){
        if(k[i]<=1){
            s.push(i);
        }
    }
    while(!s.empty()){
        int i=s.top();
        //cout<<i<<" ";
        s.pop();
        for(int j=0;j<n;j++){
            if(p[i][j]!=0){
                k[j]--;
                if(k[j]==1){
                    s.push(j);
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        if(k[i]>=2){
            //cout<<k[i]<<" ";
            return true;
        }
    }
    return false;
 }
int main()
{
    //克鲁斯卡尔算法，求最小生成树
    int m,n;//m个顶点
    while(cin>>m){
        if(m==0){
            break;
        }
        //定义有关顶点的二维数组，用来存储边//初始化为0
        int **k=new int*[m];
        for(int i=0;i<m;i++){
            k[i]=new int[m];
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                k[i][j]=0;
            }
        }
        n=m*(m-1)/2;//输入n组边的信息
        //定义边的数组
        edge *e=new edge[n];
        int start,end,weight,state;
        int j1=0;
        //输入边的信息
        for(int i=0;i<n;i++){
            cin>>start;
            cin>>end;
            cin>>weight;
            cin>>state;
            if(state==0){
                e[j1].start=start-1;
                e[j1].end=end-1;
                e[j1].weight=weight;
                e[j1++].state=state;
            }else{
                k[start-1][end-1]=weight;
                k[end-1][start-1]=weight;
            }
        }
        //对边的权值按照从小到大进行排序，使用快速排序方法
        kp(e,0,j1-1);

int sum=0;
        //每次将排序过后的边的依次加入k中，同时看加入之后是否形成环，如果形成环就跳过，进行下一个边的判断
        //判断无向图是否是环，采用拓扑排序的方法，具体操作，上面有注释
        for(int i=0;i<j1;i++){
            k[e[i].start][e[i].end] =e[i].weight;//k存放的是组成最小生成树的边
            k[e[i].end][e[i].start] =e[i].weight;//因为是无向图，所以最终形成的是一个对称的二维数组
            sum+=e[i].weight;
            if (tuopu(k,m)){//如果k是环，就将刚刚置为数字的重新置为0
                k[e[i].start][e[i].end] =0;
                k[e[i].end][e[i].start] =0;
                sum-=e[i].weight;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

```

0.0分

1 人评分

本文分类：题解列表
浏览次数：287 次浏览
发布日期：2020-05-03 19:10:23
本文链接：https://blog.dotcpp.com/a/69989

上一篇 > C语言训练-求s=a+aa+aaa+aaaa+aa...a的值-题解（C++代码）
下一篇 > 校门外的树-题解（C语言代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

继续畅通工程-题解（C++代码）

评论列表共有 2 条评论

发表评论取消回复

继续畅通工程-题解（C++代码）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 2 条评论

发表评论 取消回复

评论列表共有 2 条评论

发表评论取消回复