文章
9
粉丝
40
获赞
95
访问
3.8k
使用克鲁斯卡尔算法,输入过程中,当s==1时,直接合并,使用sort按权值从小到大排序,然后依次取出权值最小且没有修建的边,权值累加,有什么问题,求解答?
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int p[N];
struct EDGE{
int a,b,w,s;
}edge[N*N];
bool cmp(EDGE e1,EDGE e2){
return e1.w<e2.w;
}
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main(){
int n,m;
while(cin>>m){
if(m==0) break;
n = m*(m-1)/2;
for(int i = 0;i < m;i ++) p[i] = i;
for(int i = 0;i < n;i ++){
int x,y,w,s;
cin>>x>>y>>w>>s;
if(s == 1){ //s==1,直接合并
int a = find(x),b = find(y);
if(a != b) p[a] = b;
}
edge[i] = {x,y,w,s};
}
sort(edge,edge+n,cmp);
long long ans = 0;
for(int i = 0;i < n;i ++){
int a = edge[i].a,b = edge[i].b,w = edge[i].w,s = edge[i].s;
...
登录后发布评论
for(int i = 0;i < m;i ++) p[i] = i;
看起来不太对劲