Hud 1863 畅通工程[MST(kruscal)]

本文主要是介绍Hud 1863 畅通工程[MST(kruscal)]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：点击打开链接

最简单的最小生成树(WA了2次，对路的排序出了点错)。

#include<cstdio>
#include<algorithm>
using namespace std;
const int Max=5000;
const int N=105;
int n,m,father[N];
struct Rode
{int a,b;int lenth;
}rode[Max];
void Init()
{for(int i=0;i<=n;i++)father[i]=i;
}
bool cmp(Rode a,Rode b)
{if(a.lenth<b.lenth) return true;return false;
}
int find(int x)
{if(x!=father[x])father[x]=find(father[x]);return father[x];
}
int kruscal()
{int min=0;sort(rode,rode+m,cmp);//这里的开始排了n条路.for(int i=0;i<m;i++){int x=find(rode[i].a);int y=find(rode[i].b);if(x!=y){father[x]=y;min+=rode[i].lenth;}}int f=find(n),k=0;for(int i=1;i<=n;i++)if(find(i)==f) k++;if(k==n) return min;else return -1;
}
int main()
{while(scanf("%d%d",&m,&n)&&m){Init();for(int i=0;i<m;i++)scanf("%d%d%d",&rode[i].a,&rode[i].b,&rode[i].lenth);int flag=kruscal();if(flag!=-1) printf("%d\n",flag);else printf("?\n");}
}

又一次WA在了细节上。

这篇关于Hud 1863 畅通工程[MST(kruscal)]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---