51nod 1212 无向图最小生成树（prim，kruskal模板）

51nod 1212 无向图最小生成树

**prim算法模板：**
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define INF 0x3f3f3f
#define pi acos(-1.0)
#define MAX 1000010
#define N 1050

int n,m;        //N为点的数量，M为边的数量。
int G[N][N];    //建图邻接矩阵
int vis[N];     //标记数组
int dis[N];     //每点到现有集合的距离数组
void init()
{
for(int i = 1; i <= n; i++)
    {
for(int j = 1; j <= n; j++)
        {
if(i == j) G[i][i] = 0;
else G[i][j] = INF;
        }
    }
}
int prim(int begin)
{
int ans = 0;
memset(vis,0,sizeof(vis));
for(int i = 1 ; i <= n; i++)
        dis[i] = INF;
//初始化
    dis[begin] = 0;     //起点
for(int i = 1; i <= n; i++)  //操作n次
    {
int MIN = INF;
int next;
for(int j = 1; j <= n; j++) //寻找距现有集合最小点
        {
if(!vis[j] && dis[j] < MIN)
            {
                MIN = dis[j];
                next = j;
            }
        }
if(MIN == INF)
break;
        ans += MIN;
        vis[next] = 1;
for(int j = 1; j <= n; j++)  //更新
        {
if(!vis[j] && dis[j] > G[next][j])
                dis[j] = G[next][j];
        }
    }
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
    init();     //初始化
while(m--)  //举列各边
    {
int a,b,v;  //前点，后点，距离
scanf("%d%d%d",&a,&b,&v);
if(G[a][b] > v) //防重复
            G[a][b] = G[b][a] = v;
    }
int ans = prim(1);
printf("%d\n",ans);
return 0;
}

**kruskal算法模板：**
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define INF 0x3f3f3f
#define pi acos(-1.0)
#define MAX 1000010
#define M 51050

int n,m;        //N为点的数量，M为边的数量。
struct Eage    //建边图
{
int x,y,v;
}e[M];
bool cmp(Eage a,Eage b) //排序需要
{
return a.v < b.v;
}
int fa[M];  //祖先数组
void init() //初始化祖先数组
{
for(int i = 1; i <= n; i++)
        fa[i] = i;
}
int Find(int x) //查找祖先
{
if(fa[x] != x)
        fa[x] = Find(fa[x]);
return fa[x];
}
int kruskal()
{
int ans = 0;
int k = 0;
    sort(e,e+m,cmp);    
for(int i = 0; i < m; i++)  //最小边开始
    {
int dx = Find(e[i].x);  
int dy = Find(e[i].y);
if(dy != dx)    //如果祖先不相等合并
        {
            fa[dx] = dy;
            ans += e[i].v;
            k++;
        }
if(k == n-1)    //找完
break;
    }
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 0; i < m; i++)
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v);
    init();
int ans = kruskal();
printf("%d\n",ans);
return 0;
}