最小生成樹模板

prim：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int inf=1000000;
const int maxn=105;
int mat[maxn][maxn],dis[maxn];
bool vis[maxn];
int n,ans;

bool prim()
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
        dis[i]=inf;
    ans=0;dis[0]=0;
    for(int i=0;i<n;i++)
    {
        int temp=inf,k=0;
        for(int j=0;j<n;j++)
        {
            if(!vis[j] && dis[j]<temp )
            {
                temp=dis[j];
                k=j;
            }
        }
        if(temp==inf)
            return false;
        vis[k]=true;
        ans+=temp;
        for(int j=0;j<n;j++)
        {
            if(!vis[j] && dis[j]>mat[k][j])
                dis[j]=mat[k][j];
        }
    }
    return true;
}