[编程笔记]-Prim

实现

和Dijkstra基本一模一样。

不过它每次找的是距离当前生成的树最近的节点，不是距离树根最近的节点。

[编程笔记]-Dijkstra(Plain)迪杰斯特拉（朴素版）

1. 初始化：设立一个集合S（空）储存所有已在生成树中的点，并设立距离dis数组，除了起点设为0外，其他点都设为正无穷。
2. 在所有点中，找一个不在S里并且dis最小的点t
3. 把t加入集合S，并且更新所有与之相连的点的距离。
4. 重复执行2、3步直到所有点都加入集合S（共执行n次）。

注：Dij共迭代n-1次，因为开头指定了一个起点；但Prim并没有，所以执行n次。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=505;

int g[N][N];
int dis[N];
bool fns[N]={false};

int n,m;
int u,v,w;

bool prim(){
    int res=0;
    dis[1]=0;
    for(int t=0;t<n;t++){
        int mi=0;
        for(int i=1;i<=n;i++){
            if(!fns[i]&&dis[i]<dis[mi])mi=i;
        }
        if(mi==0)return false;
        fns[mi]=true;
        res+=dis[mi];
        for(int i=1;i<=n;i++){
            if(g[mi][i]!=0x3f3f3f3f){
                dis[i]=min(dis[i],g[mi][i]);
            }
        }
    }
    cout<<res;
    return true;
}

int main(){
    cin.tie(0);
    cin>>n>>m;
    memset(g,0x3f,sizeof(g));
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        g[u][v]=min(g[u][v],w);
        g[v][u]=g[u][v];
    }
    if(!prim())cout<<"impossible";
    return 0;
}

完结撒花o(￣︶￣)o