「最小生成树」Prim

Luogu P3366

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+5;
int ans=0;
int A,B;
int q[maxn][maxn],dis[maxn],book[maxn];
int main(){
scanf("%d%d",&A,&B);
for(int i=1;i&lt;=B;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(!q[x][y])
q[x][y]=q[y][x]=z;
else
q[x][y]=q[y][x]=min(q[x][y],z);
}
for(int i=1;i<=A;i++) dis[i]=0x7fffffff;//最小生成树初始化
dis[1]=0;
for(int i=1;i<=A;i++){
int mindt=0x7fffffff,k;
for(int j=1;j&lt;=A;j++)
if(!book[j] && dis[j]<mindt){
mindt=dis[j];
k=j;
}
if(mindt==0x7fffffff){//没有最小生成树(即图不连通)
printf("orz\n");
return 0;
}
ans+=mindt;//加上本次找到的最短安全边
book[k]=1;
for(int j=1;j&lt;=A;j++)
if(!book[j] && q[k][j] && q[k][j]<dis[j]) dis[j]=q[k][j];
}
printf("%d\n",ans);
return 0;
}