有一些地方需要鋪蓋電纜，這些地方兩點間的路可能不止一條，需要求出來至少需要多少電纜才能讓所有的點都連接起來，當然，間接連接也算。
/#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
using?namespace?std;

#define?maxn?105

struct?node
{
????int?u,?v,?len;
????friend?bool?operator?<?(node?a,?node?b)
????{
????????return?a.len?>?b.len;
????}
};
int?f[maxn];

int?Find(int?x)
{
????if(f[x]?!=?x)
????????f[x]?=?Find(f[x]);
????return?f[x];
}

int?main()
{
????int?N,?M;

????while(scanf("%d",?&N)?!=?EOF?&&?N)
????{
????????int?i,?ans=0;
????????priority_queue<node>Q;
????????node?s;

????????for(i=0;?i<=N;?i++)
????????????f[i]?=?i;
????????scanf("%d",?&M);

????????while(M--)
????????{
????????????scanf("%d%d%d",?&s.u,?&s.v,?&s.len);
????????????Q.push(s);
????????}

????????while(Q.size())
????????{
????????????s?=?Q.top();Q.pop();

????????????int?u?=?Find(s.u),?v?=?Find(s.v);

????????????if(u?!=?v)
????????????{
????????????????f[u]?=?v;
????????????????ans?+=?s.len;
????????????}
????????}

????????printf("%d\n",?ans);
????}

????return?0;
}

轉載于:https://www.cnblogs.com/liuxin13/p/4674370.html

總結

以上是生活随笔為你收集整理的B - Networking - poj 1287的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。