#如上，prim 算法
···cpp
```cpp
#include <cstdio>
#include <cstring>
#define N 5011
#define M 200011
int fst[N],nxt[M],e[M],v[M],pos = 0,n,m;
int dis[N],now,ans = 0;
bool in[N];
void AddEdge(int a,int b,int c){
if(a == 1)dis[b] = c;
pos++;
nxt[pos] = fst[a];
fst[a] = pos;
e[pos] = b;
v[pos] = c;
}
int main()
{
memset(in,0,sizeof in);
memset(fst,-1,sizeof fst);
memset(dis,0x7f,sizeof dis);
scanf("%d %d",&n,&m);
for(int i = 1;i <= m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
AddEdge(a,b,c);
AddEdge(b,a,c);
}
in[1] = 1;
while(1){
bool flag = 1;
int mn = 0x7ffffff,x;
for(int j = 1;j <= n;j++){
if(!in[j]){
if(dis[j] < mn){
mn = dis[j];
x = j;
}
flag = 0;
}
}
if(flag)break;
in[x] = 1;
ans += dis[x];
for(int j = fst[x];j != -1;j = nxt[j]){
if(v[j] < dis[e[j]]){
dis[e[j]] = v[j];
}
}
}
printf("%d",ans);
return 0;
}
···
```
by yingzifan @ 2017-08-08 11:05:08
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 9999999
#define N 5005
int map[N][N];
int used[N];
int dist[N];
int n,m;
int ans=0;
void prim()
{
memset(used,0,sizeof(used));
for(int i=1;i<=n;i++)dist[i]=map[1][i];
used[1]=1;
int k,minn;
for(int i=1;i<n;i++)
{
minn=INF;
for(int j=1;j<=n;j++)
{
if(!used[j]&&dist[j]<minn)
{
minn=dist[j];
k=j;
}
}
ans+=minn;
used[k]=1;
for(int j=1;j<=n;j++)
{
if(!used[j]&&dist[j]>map[j][k])
{
dist[j]=map[j][k];
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)map[i][j]=INF;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
map[x][y]=map[y][x]=min(map[x][y],z);
}
prim();
bool ok=true;
for(int i=1;i<=n;i++)
if(!used[i])ok=false;
if(ok)printf("%d\n",ans);
else printf("orz\n");
}
```
by 墨明棋妙 @ 2017-08-12 20:12:18
孩子还是安心打模板吧
by 墨明棋妙 @ 2017-08-12 20:13:33