最小生成树MST

一、最小生成树MST

1.Kruskal算法

按照边的权值由小到大排序查看一遍，如果该边的两顶点不在同一连通分量里，则加入最小生成树中，可用并查集高效的判断两点是否在同一连通分量中；

例：hdu1863畅通工程

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

Sample Input

3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100

Sample Output

3 ?

#include <iostream>
#include <algorithm>
//kruskal将边排序，再贪心从最小边开始选取，用并查集维护MST的连通性;
using namespace std;
typedef long long ll;
const int maxn=102;
int n,m;
struct edge{
    int from,to;
    ll cost;
};
edge e[maxn*maxn];
bool cmp(edge x,edge y)
{
    return x.cost<y.cost;
}
int par[maxn];
int init()
{
    for(int i=1;i<=m;i++)
        par[i]=i;
}
int fin(int x)
{
    return par[x]==x?x:par[x]=fin(par[x]);
}
bool sam(int x,int y)
{
    return fin(x)==fin(y);
}
void unit(int x,int y)
{
    x=fin(x),y=fin(y);
    if(x==y) return;
     par[y]=x;
}
ll kruskal()
{
    sort(e+1,e+n+1,cmp);
    init();
    ll res=0;
    for(int i=1;i<=n;i++)
    {
        if(sam(e[i].from,e[i].to))continue; //两顶点已连通；
        unit(e[i].from,e[i].to);
        res+=e[i].cost;
    }
    return res;
}
int main()
{
    while(cin >> n >>m,n)
    {
        ll ans=0;
        for(int i=1;i<=n;i++)
            cin >> e[i].from >> e[i].to >> e[i].cost;
        ans=kruskal();
        for(int i=1;i<=m;i++)
            if(!sam(i,1)){
                ans=-1;
            }
        if(ans==-1)
            cout << "?" << endl;
        else
        cout << ans << endl;
    }
    return 0;
}

例：POJ2421 Constructing Roads

Description

There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.

We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.

Input

The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.

Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.

Output

You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.

Sample Input

Sample Output

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=102;
int n,par[maxn];
struct edge{
    int from,to;
    ll cost;
    bool operator< (const edge& x)const{
            return x.cost<cost;
    }
};
priority_queue<edge> que;
void init()
{
    for(int i=1;i<=n;i++)
        par[i]=i;
}
int fin(int x){
    return par[x]==x?x:par[x]=fin(par[x]);
}
bool sam(int x,int y){
    return fin(x)==fin(y);
}
void unit(int x,int y)
{
    x=fin(x),y=fin(y);
    if(x==y)return;
    par[y]=x;
}
ll kruskal()
{
    ll res=0;
    while(!que.empty())
    {
        edge e=que.top();
        que.pop();
        if(!sam(e.from,e.to))
        {
            res+=e.cost;
            unit(e.from,e.to);
        }
    }
    return res;
}
int main()
{
    int m;
    cin >> n;
    edge e;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin >> e.cost;
            e.from=i,e.to=j;
            if(i!=j)
                que.push(e);
        }
    }
    init();
    cin >> m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin >> a >> b;
        unit(a,b);
    }
    ll ans=kruskal();
    cout << ans << endl;
    return 0;
}

2、Prim算法

首先，假设有一棵只包含一个顶点v的树T,然后贪心的选取T和其他顶点相邻的最小权值的边，并把它加入到T中。不断进行这个操作，就可以得到一棵最小生成树。

例：hdu1863畅通工程

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=102;
struct edge{
    int to;
    ll cost;
    edge(int x,ll y):to(x),cost(y){}
    edge(){}
    bool operator< (const edge &x)const{
        return x.cost<cost;
    }
};

priority_queue<edge> que;   //选取与T相邻代价最小的边;
vector<edge> G[maxn];       //对每个点存与之相邻的所有边的信息;(邻接表)
int n,m;
bool vis[maxn];             //标记已连接的点;

ll prim()
{
    ll res=0;
    vis[1]=1;               //选取一个初的顶点为树T;
    for(int i=0;i<G[1].size();i++)
        que.push(G[1][i]);  //将与1相邻的所有边放入队列;
    while(que.size())
    {
        edge tmp=que.top();
        que.pop();
        if(vis[tmp.to])continue;
        vis[tmp.to]=1;
        res+=tmp.cost;
        for(int i=0;i<G[tmp.to].size();i++)
            que.push(G[tmp.to][i]);
    }
    return res;
}
int main()
{
    while(cin >> n >> m,n)
    {
        for(int i=0;i<=m;i++)
            G[i].clear();
        while(que.size())que.pop();
        memset(vis,0,sizeof(vis));  //初始化清空
        for(int i=1;i<=n;i++)       //存取所有边的信息;
        {
            int u,v;
            ll cost;
            cin >> u >> v >> cost;
            G[u].push_back(edge(v,cost));
            G[v].push_back(edge(u,cost));
        }
        ll ans=prim();
        for(int i=1;i<=m;i++)       //判断是否连通
            if(!vis[i])
                ans=-1;
        if(ans==-1)
            cout << "?" << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

例：POJ1258 Agri-Net

Description

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.

Input

The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.

Output

For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

Sample Input

Sample Output

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=102;
struct edge{
    int to;
    ll cost;
    edge(int x,ll y):to(x),cost(y){}
    edge(){}
    bool operator< (const edge& xx) const{
        return xx.cost<cost;
    }
};
priority_queue<edge> que;
ll G[maxn][maxn]; //邻接矩阵;
int n;
bool vis[maxn];
ll prim()
{
    ll res=0;
    vis[1]=1;
    for(int i=2;i<=n;i++)   //该点相邻的点均入队列;
        que.push(edge(i,G[1][i]));
    while(!que.empty())
    {
        edge e=que.top();
        que.pop();
        if(vis[e.to])continue;
        res+=e.cost;
        vis[e.to]=1;
        for(int i=1;i<=n;i++)//新加入的点的相邻边入队列;
            if(i!=e.to)
                que.push(edge(i,G[e.to][i]));
    }
    return res;
}
int main()
{
    while(cin >> n)
    {
        memset(vis,0,sizeof(vis));
        while(!que.empty()) que.pop();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin >> G[i][j];
        ll ans=prim();
        cout << ans << endl;
    }
    return 0;
}