題目

一個無向圖，求最小生成樹里權值最大的那條邊

輸入

第一行有兩個整數n,m表示有n個店，m條邊。接下來m行是對每條邊的描述，u, v, c表示點u和v之間有邊，權值為c。(1≤n≤300，1≤c≤10000)
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

輸出

兩個整數s, max，表示你有幾條邊，權值最大的那條邊的權值是多少。
3 6

---

解題思路

我們知道最小生成樹一點是n-1條邊的，然后求最大值很簡單

---

代碼

#include<cstdio> #include<iostream> using namespace std; int n,k,cost[301][301],lowcost[301],x,y,w,s,last,maxs; bool ok[301]; int main() {scanf("%d%d",&n,&k);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++) cost[i][j]=23333333;//初始化for (int i=1;i<=k;i++){scanf("%d%d%d",&x,&y,&w);cost[x][y]=w;cost[y][x]=w;//聯通}for (int i=1;i<=n;i++) lowcost[i]=cost[1][i];//離集合的距離ok[1]=true;//封路for (int i=2;i<=n;i++){int k=0,mins=23333333;for (int j=1;j<=n;j++)if (!ok[j] && lowcost[j]<mins){mins=lowcost[j];k=j;}//求最近點ok[k]=true;//封路s=max(s,lowcost[k]);//求最大值for (int j=1;j<=n;j++)if (lowcost[j]>cost[k][j]) lowcost[j]=cost[k][j]; //修正離集合最近的距離}printf("%d %d",n-1,s);//輸出 }

總結

以上是生活随笔為你收集整理的ssl2345-繁忙的都市的全部內容，希望文章能夠幫你解決所遇到的問題。

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