https://www.acwing.com/problem/content/860/
這道題可以這樣理解，在一個圖（別人管這叫集合）里面（圖論嘛，類似于路線圖）中選出所有的點，用n-1條線段，把這些點都連著，題意很好理解，我也當時想著用貪心的思路來做，后來發現并不是很好做，然后我就看了y總的做法，也是根據貪心提出了一個prim的演算法，y總可能講的不是很仔細，但是思路是沒有錯的，我看了b站的視頻，確實有助于理解，于是我也拿出來給大家看，這個視頻盡量多看幾遍，這是原理，
https://www.bilibili.com/video/BV1Ma4y1W7pJ?from=search&seid=2724484141940561544
主要的意思就是，st[i]保存的節點看作一個集合，然后去擴散下一個點，居然和迪杰特斯拉演算法有異曲同工之處，y總dist[i]沒說清，我覺得根據題意來說，dist[i]應該是離上一個點牽著的距離（我也不是很清楚）dist會隨著演算法變化，因為新增了st,所以根據這些點進行擴散，我的話都是根據視頻去說，代碼中很細節的地方我都注釋了，
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=1e5+10,Inf=0x3f3f3f3f;
int g[N][N],dist[N];
bool st[N];
int n,m;
int prim()
{
int res=0;
memset(dist,0x3f,sizeof dist);
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]))//這個表示找離已經保存的點最近的距離，
t=j;
}
// cout<<t<<" "<<dist[t]<<endl;
if(i&&dist[t]==Inf) return Inf;//說明沒有到t點的路線，t是孤立點，
if(i) res+=dist[t];//加n-1次，這又是一個小細節哦，然后dist[t]要找的最小距離，
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],g[t][j]);
}
st[t]=true;
}
return res;
}
int main(void)
{
memset(g,0x3f,sizeof g);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=min(g[a][b],c);
g[b][a]=min(g[b][a],c);
}
int t=prim();
if(t==Inf) puts("impossible");
else
cout<<t;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261457.html
標籤：其他