kruskal(原理讲解）
//用克鲁斯卡尔算法来求最小生成树（畅通工程）
首先，整一个结构体数组来记录两个顶点及花费，按照自定义的sort函数对结构体数组进行排序，然后利用并查集对数组一个个的进行判断两条边是否连通，若未连通，则利用并查集将其连通并且记录花费，同时统计一个增加的边的条数用来判断整个村庄最后是否能连通。
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <string>
using namespace std;
//
struct node{
int a,b,m;
};
int cmp(node a,node b)
{
return a.m<b.m;
}
int fa[102];
int find(int x){
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
int main() {
int N,M;
while (cin>>N>>M) {
if(N==0) return 0;
for(int i=0;i<102;++i){
...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发