【prim + kruscal 】最小生成树模板

来源：dlut oj

1105: Zhuo’s Dream

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 40 Solved: 14
[Submit][Status][Web Board]

Description

Zhuo is a lovely boy and always make day dream. This afternoon he has a dream that he becomes the king of a kingdom called TwoBee.

In the dream Zhuo faced a hard situation: he should make a traffic construction plan for the kingdom. We have known that the kingdom consists of N cities and M dirt roads, it’s very uncomfortable when travelling in the road. Now he would choose some roads to rebuild to concrete road. To avoid called TwoBee by the common people, Zhuo wants to show some excellent thing to this world while it needs your help. He wants his plan achieve two goals:

1. We should choose just N-1 roads to rebuild. After rebuild we can also travel between any two cities by the concrete roads.

2. We want to minimize the longest length among the chosen roads.

So you should write a program to calculate the total length of the chosen roads.

Input

There are multiple test cases.

The first line contains two integers N and M. (1 <= N <= 100, 1 <= M <= 10000)

In the next M lines, each line contains three integers a, b, w, indicating that there is a dirt road between city a and city b with length w. (1 <= a, b <= N, 1 <= w <= 1000)

Output

For each test case, output an integer indicating the total length of the chosen roads. If there is no solution, please output -1.

Sample Input

3 3

1 2 1 1 3 1 2 3 3

Sample Output

HINT

Source

Rainy

prim算法

#include <cstdio>
#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=102;
const int inf=1<<30;
int map[maxn][maxn];
int dis[maxn];
bool flag[maxn];
int a,b,c,n,m,ans;
 
void init()
{
    memset(map,-1,sizeof(map));
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(map[a][b]==-1 || c< map[a][b])
        {
            map[a][b]=map[b][a]=c;
        }
    }
}
 
void prim()
{
    memset(flag,false,sizeof(flag));
    for(int i=1;i<=n;i++)dis[i]=inf;
    dis[1]=0;
    ans=0;
    for(int j=1;j<=n;j++)
    {
        int now,value=inf;
        for(int i=1;i<=n;i++)
        {
            if(flag[i]==false && dis[i]<value)
            {
                value=dis[i];
                now=i;
            }
        }
        if(value==inf)
        {
            cout << "-1" <<endl;
            return;
        }
        flag[now]=true;
        ans+=dis[now];
        for(int i=1;i<=n;i++)
        {
            if(!flag[i] && map[now][i]!=-1 && dis[i]>map[now][i])
            dis[i]=map[now][i];
        }
    }
     cout << ans <<endl;
}
 
int main()
{
    //'freopen("in.txt","r",stdin);
    while(cin >> n >> m)
    {
        init();
        prim();
    }
    return 0;
}

下面是最小生成树的Kruskal算法，这个算法原理看起来很复杂，但实现起来很简单：开始的时候是每个顶点一棵树，并将边按权重升序排列。然后从前到后按循序选边，如果当前选择的边的两个顶点分在两棵不同的树中，则将该边加入到最小生成树中，并合当前边连接的两棵树，如果边得两个顶点在相同的树中，则不做任何处理,需要注意的是这个算法是针对无向连通图的,如果是有限图,则需要在算法中做些处理,但算法原理是一样的。

kruskal算法：

#include <cstdio>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn=10002;
int m,n;
int cnt,length;
int parent[maxn];
 
struct node
{
    int from;
    int to;
    int val;
}s[maxn];
 
bool cmp(const node &l,const node &r)
{
    return l.val<r.val;
}
 
void init()
{
    for(int i=0;i<maxn;i++)
    {
        parent[i]=i;
    }
}
 
int find(int x)
{
    while(x!=parent[x])
    {
        x=parent[x];
    }
    return x;
}
 
void merge(int a,int b,int val)
{
    int roota=find(a);
    int rootb=find(b);
    if(roota!=rootb)
    {
        cnt++;
        parent[rootb]=roota;
        length+=val;
    }
}
 
void kruskal()
{
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++)
    {
        merge(s[i].from,s[i].to,s[i].val);
        if(cnt==m-1)break;
    }
    if(cnt<m-1)
    {
        length=-1;
    }
}
 
int main()
{
   // freopen("in.txt","r",stdin);
    while(cin >> m >> n)
    {
        init();
        cnt=0,length=0;
        memset(s,0,sizeof(s));
        for(int i=0;i<n;i++)
        {
              cin >> s[i].from >> s[i].to >> s[i].val;
        }
       kruskal();
        cout << length <<endl;
    }
    return 0;
}