kruskal和prim最小生成树算法

Author：子不语
发布时间：November 13, 2019
1884views
No comments
1269 words
Categories：算法和其模板

最小生成树

最小生成树的应用

1.最大边权最小的生成树

直接求最小生成树，因为最小生成树的最大边一定是所有生成树里最大边权最小的

2.次小生成树

枚举最小生成树上的 n条边,对于其中某条边,从图中删除它以后计算剩余图的最小生成树，一共n-1棵，从这n-1棵生成树中找出最小的一棵，就是整个图的次小生成树。

3.边权极差最小生成树

给定一个无向连通图，求出它的所有的生成树中，最大边权和最小边权只差最小的生成树。

枚举所有的生成树。

kruskal最小生成树算法

思路

将所有的边按从小到大排序，一次考虑每条边，如果将这个边加入最小生成树内不构成环，则加入，反之则不能加入。

演示

1557485052272

对于这棵树的最小生成树每次加入边的顺序为：

1557485172691

四道模板题：

第一道：布设光纤

描述：

蒜国有 n 座基站，现在蒜头君想给基站之间布设光纤，使得任意两座基站都是连通的，光纤传输具有传递性，即如果基站 A 和基站 B 之间有光纤，基站 B 和基站 C 之间有光纤，则基站 A 和基站 C 也是连通的，可以通过中间基站 B 来完成传输。
不同的基站之间布设光纤的费用是不同的，现在蒜头君知道了任意两座基站之间布设光纤的费用，求问如何布设，可以使得任意两座基站都是连通的，且总费用最小。
输入格式
第一行输入一个整数 n(2≤n≤100)，表示蒜头基站总数。
接下来输入 n×n 的矩阵。第 i 行第 j 列的整数表示第 i 座基站和第 j 座基站之间布设光纤的费用 wij（0≤wij ≤10,000）。
输出格式
输出一个整数，表示布设光纤的最小总费用，且使任意两座基站都是连通的。
样例输入
4
0 1 5 1
1 0 6 3
5 6 0 2
1 3 2 0
样例输出

include<iostream>

include<algorithm>

using namespace std;
const int maxn = 1e5+5;
int map105;
int fa[maxn];
struct node{

int from;
int to;
int len;

}arr[maxn];
bool cmp(node a,node b)
{

return a.len<b.len;

}
void init()
{

for(int i=1;i<maxn;++i)
{
    fa[i]=i;
}

}
int find(int x)
{

if(x!=fa[x])
{
    fa[x]=find(fa[x]);
}
return fa[x];

}
void merge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    fa[p]=q;
}

}
bool judge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    return true;
}
return false;

}
int main()
{

int n;
while(cin>>n)
{
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            cin>>map[i][j];    
        }    
    }
    int stc=0;    
    for(int i=0;i<n;++i)
    {
        for(int j=i;j<n;++j)
        {
            arr[stc].from = i;
            arr[stc].to = j;
            arr[stc++].len = map[i][j];
        }
    }
    sort(arr,arr+stc,cmp);
    init();
    int cnt=0;
    int sum = 0;
    for(int i=0;i<stc;++i)
    {
        if(judge(arr[i].from,arr[i].to))
        {
            cnt++;
            merge(arr[i].from,arr[i].to);
            sum+=arr[i].len;
            if(cnt==n-1)
            {
                break;
            }
        }    
    }
    cout<<sum<<endl;
} 
return 0;

}

第二道：连线问题

问题描述

蒜头君和花椰菜君经常出难题考对方。一天，花椰菜君给蒜头君出了这样一道难题：花椰菜君在坐标系上随机画了 N 个点，然后让蒜头君给点之间连线，要求任意两点之间都是连通的，且所连的线段长度之和最小。聪明的你快来帮蒜头君解决一下吧。
输入格式
第一行输入一个整数 N(1≤N≤100)，表示花椰菜君一共画了 N 个点。然后输入 N 行，每行输入两个整数 x,y（0≤x,y≤1,000），代表一个点的坐标。
输出格式
输出一行，输出一个实数，表示所连线段长度之和的最小值（结果四舍五入保留两位小数）。
样例输入
4
1 1
2 2
3 3
3 1
样例输出

4.24

include <iostream>

include <algorithm>

include <cmath>

using namespace std;
const int maxn = 1e6+5;
int fa[maxn];
int x[maxn];
int y[maxn];
void init()
{

for(int i=1;i<maxn;++i)
{
    fa[i]=i;
}

}
int find(int x)
{

if(x==fa[x])
{
    return x;
}    
return fa[x] = find(fa[x]);

}
void merge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    fa[p]=q;
}

}
bool judge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    return true;
}
return false;

}
struct node
{

int from;
int to;
double len;

}arr[10005];
bool cmp(node a,node b)
{

return a.len<b.len;

}
int main()
{

int n;
cin>>n;
for(int i=0;i<n;++i)
{
    cin>>x[i]>>y[i];
}
int top=0;
for(int i=0;i<n;++i)
{
    for(int j=0;j<n;++j)
    {
        if(i!=j)
        {
            double dist = sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
            int from = x[i]*100+y[i];
            int to = x[j]*100+y[j];
            arr[top].from = from;
            arr[top].to = to;
            arr[top++].len = dist;    
        }
    }
}
sort(arr,arr+top,cmp);
init();
double sum = 0;
int cnt = 0;
for(int i=0;i<top;++i)
{
    if(judge(arr[i].from,arr[i].to))
    {
        merge(arr[i].from,arr[i].to);
        cnt++;
        sum+=arr[i].len;
        if(cnt==n-1)
        {
            break;
        }
    }    
}
//cout<<sum<<endl;
printf("%.2lf\n",sum);
return 0;

}

第三道：穿越雷区

问题描述

蒜头君最近迷上了一款 RPG 游戏，这次他要去森林里的 n 个宝藏点收集宝藏，编号从 1 到 n。森林里有 m 条道路连接宝藏点，每条道路上都有数量不等的地雷，蒜头君想从中找出若干条道路，使得任意两个宝藏点都是连通的，这样蒜头君都能访问到每个宝藏点了。另外，由于遇到一个地雷，蒜头君会减少一定的血量。
现在蒜头君知道了这 m 条道路上的地雷数，蒜头君希望挑选若干条道路，使得挑选出的道路，地雷数量之和尽可能小。
输入格式
第一行输入两个整数 n,m（1≤n≤30,000，1≤m≤50,000），表示森林里有 n个宝藏点，m 条道路。两个宝藏点之间可能会有多条道路。
接下来输入 m 行，每行输入三个整数 x，y，z（1≤x,y≤n，0≤z≤1,000），表示 x 和 y 之间有 z 个地雷。
输出格式
输出一行，输出一个整数。表示蒜头君挑出了若干条道路，使得任意两个宝藏点都是连通的，输出道路的地雷数量之和最小值。
样例输入
3 4
1 2 121
1 3 202
2 1 497
2 3 135
样例输出

256

include <iostream>

include <algorithm>

include <cmath>

using namespace std;
const int maxn = 3e4+5;
int fa[maxn];
void init()
{

for(int i=1;i<maxn;++i)
{
    fa[i]=i;
}

}
int find(int x)
{

if(x==fa[x])
{
    return x;
}    
return fa[x] = find(fa[x]);

}
void merge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    fa[p]=q;
}

}
bool judge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    return true;
}
return false;

}
struct node
{

int from;
int to;
double len;

}arr[50005];
bool cmp(node a,node b)
{

return a.len<b.len;

}
int main()
{

int n,m;
while(cin>>n>>m)
{
    int a,b,len;
    for(int i=0;i<m;++i)
    {
        cin>>arr[i].from>>arr[i].to>>arr[i].len;
    }
    sort(arr,arr+m,cmp);
    init();
    int sum = 0;
    int cnt=0;
    for(int i=0;i<m;++i)
    {
        if(judge(arr[i].from,arr[i].to))
        {
            merge(arr[i].from,arr[i].to);
            sum+=arr[i].len;
            cnt++;
            if(cnt==n-1)
            {
                break;
            }    
        }
    }
    cout<<sum<<endl;
}
return 0;

}

第四道：高速公路

问题描述

蒜头君所在的国家有 n 个城市，现在需要在城市之间修高速公路，有 m 条修路的方案，每个方案表示 a, b 城市之间修一条限速为 c 的高速公路。蒜头君希望从这 m 个方案中选出若干方法试行，能够让 n 座城市联通，并且希望所有高速公路中最高限速和最低限速的差值最小。
输入格式
第一行输入两个整数 n,m（2≤n≤100，1<=m<=n(n-1)/2 ），表示有 n 个城市，m 条修路方案。两个城市之间可能会有多条修路方案。
接下来输入 m 行，每行输入三个整数 a，b，c（1≤a,b≤n，0≤c≤1,0000）。
输出格式
如果修路方案不能让 nn 个城市之间联通，输出 -1，否者输出最小的差值。
样例输入
4 4
1 2 2
2 3 4
1 4 1
3 4 2
样例输出

include <iostream>

include <algorithm>

include <cmath>

using namespace std;
const int maxn = 3e4+5;
int fa[maxn];
void init()
{

for(int i=1;i<maxn;++i)
{
    fa[i]=i;
}

}
int find(int x)
{

if(x==fa[x])
{
    return x;
}    
return fa[x] = find(fa[x]);

}
void merge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    fa[p]=q;
}

}
bool judge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    return true;
}
return false;

}
struct node
{

int from;
int to;
int len;

}arr[10005];
bool cmp(node a,node b)
{

return a.len<b.len;

}
int main()
{

int n,m;
while(cin>>n>>m)
{
    int a,b,len;
    for(int i=0;i<m;++i)
    {
        cin>>arr[i].from>>arr[i].to>>arr[i].len;
    }
    sort(arr,arr+m,cmp);
    int ans = 1<<30;
    for(int i=0;i<m;++i)
    {
        int min_val = 1<<30;
        int max_val = -1<<30;
        int cnt=0;
        init();
        for(int j=i;j<m;++j)
        {
            if(judge(arr[j].from,arr[j].to))
            {
                merge(arr[j].from,arr[j].to);
                min_val = min(min_val,arr[j].len);
                max_val = max(max_val,arr[j].len);
                cnt++;    
            }    
        }
        if(cnt!=n-1)
        {
            continue;
        }
        else 
        {
            ans = min(ans,(max_val-min_val));    
        }
    }
    if(ans ==  1<<30)
    {
        cout<<"-1"<<endl;
    }
    else 
    {
        cout<<ans<<endl;
    }
}
return 0;

}

Prim最小生成树算法

Prim算法对于使用邻接矩阵表示的图来说非常方便实现，所以在求稀疏图的最小生成树的时候常用Prim算法。

模板

#define INF 0x1f1f1f1f    //定义一个整数常量，表示无穷大
// prim函数返回得到的最小生成树的n-1条边的权值和
// 参数cost 为表示图的矩阵，n为顶点个数
int prim(int cost[][200],int n)
{
    //low表示每个点到生成树的最小距离，vis表示一个点是否已经加入生成树中
    int low[10000],vis[10000]=0;        //顶点数n<10000 
    int i,j,p;
    int min,res=0;                        //res表示最小生成树权值和 
    vis[0]=1;                            //将第一个顶点加入集合S 
    for(int i=1;i<n;++i)                //并更新该顶点到其他顶点的距离 
    {
        low[i] = cost[0][i];
    }
    for(int i=1;i<n;++i)                //尝试加入剩下的n-1条边 
    {
        min = INF;                        //寻找点集V-S中距离集合S最近的距离的点 
        p=-1;                            //min为权值，p为位置 
        for(int j=0;j<n;++j)
        {
            if(0==vis[j] && min>low[j])
            {
                min = low[j];
                p = j;
            }
        }    
        //min==INF 说明找不到能够加入的点了，说明图是不连通的（已经加入的点集和未加入的点集不连通）。
        if(min==INF) return -1;
        
        res+=min;
        vis[p]=1;        //P点加入生成树的点集 
        
        for(j=0;j<n;++j)    //加入该点后更新集合S到集合V-S之间的距离 
        {
            if(vis[j]==0 && low[j]>cost[p][j])
            {
                low[j] = cost[p][j];    
            }    
        } 
    }
    return res;    
}

第一道：hdu

题目描述：

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.

#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x1f1f1f1f    //定义一个整数常量，表示无穷大
// prim函数返回得到的最小生成树的n-1条边的权值和
// 参数cost 为表示图的矩阵，n为顶点个数
int prim(int cost[][100],int n)
{
    //low表示每个点到生成树的最小距离，vis表示一个点是否已经加入生成树中
    int low[10000];
    int vis[10000]={0};        //顶点数n<10000 
    int i,j,p;
    int min,res=0;                        //res表示最小生成树权值和 
    vis[0]=1;                            //将第一个顶点加入集合S 
    for(int i=1;i<n;++i)                //并更新该顶点到其他顶点的距离 
    {
        low[i] = cost[0][i];
    }
    for(int i=1;i<n;++i)                //尝试加入剩下的n-1条边 
    {
        min = INF;                        //寻找点集V-S中距离集合S最近的距离的点 
        p=-1;                            //min为权值，p为位置 
        for(int j=0;j<n;++j)
        {
            if(0==vis[j] && min>low[j])
            {
                min = low[j];
                p = j;
            }
        }    
        //min==INF 说明找不到能够加入的点了，说明图是不连通的（已经加入的点集和未加入的点集不连通）。
        if(min==INF) return -1;
        
        res+=min;
        vis[p]=1;        //P点加入生成树的点集 
        
        for(j=0;j<n;++j)    //加入该点后更新集合S到集合V-S之间的距离 
        {
            if(vis[j]==0 && low[j]>cost[p][j])
            {
                low[j] = cost[p][j];    
            }    
        } 
    }
    return res;    
} 
int main()
{
    int a[100][100];
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                cin>>a[i][j];    
            }    
        }    
        int t,x,y;
        cin>>t;
        while(t--)
        {
            cin>>x>>y;
            a[x-1][y-1]=a[y-1][x-1]=0;
        }
        int ans = prim(a,n);
        cout<<ans<<endl;
    }
    return 0;    
}

Last modification：November 13th, 2019 at 08:43 pm

如果觉得我的文章对你有用，请随意赞赏

kruskal和prim最小生成树算法

子不语 • 2019 年 11 月 13 日

最小生成树

最小生成树的应用

1.最大边权最小的生成树

直接求最小生成树，因为最小生成树的最大边一定是所有生成树里最大边权最小的

2.次小生成树

3.边权极差最小生成树

给定一个无向连通图，求出它的所有的生成树中，最大边权和最小边权只差最小的生成树。

枚举所有的生成树。

kruskal最小生成树算法

思路

将所有的边按从小到大排序，一次考虑每条边，如果将这个边加入最小生成树内不构成环，则加入，反之则不能加入。

演示

1557485052272

对于这棵树的最小生成树每次加入边的顺序为：

1557485172691

四道模板题：

第一道：布设光纤

描述：

include<iostream>

include<algorithm>

using namespace std;
const int maxn = 1e5+5;
int map105;
int fa[maxn];
struct node{

int from;
int to;
int len;

}arr[maxn];
bool cmp(node a,node b)
{

return a.len<b.len;

}
void init()
{

for(int i=1;i<maxn;++i)
{
    fa[i]=i;
}

}
int find(int x)
{

if(x!=fa[x])
{
    fa[x]=find(fa[x]);
}
return fa[x];

}
void merge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    fa[p]=q;
}

}
bool judge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    return true;
}
return false;

}
int main()
{

int n;
while(cin>>n)
{
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            cin>>map[i][j];    
        }    
    }
    int stc=0;    
    for(int i=0;i<n;++i)
    {
        for(int j=i;j<n;++j)
        {
            arr[stc].from = i;
            arr[stc].to = j;
            arr[stc++].len = map[i][j];
        }
    }
    sort(arr,arr+stc,cmp);
    init();
    int cnt=0;
    int sum = 0;
    for(int i=0;i<stc;++i)
    {
        if(judge(arr[i].from,arr[i].to))
        {
            cnt++;
            merge(arr[i].from,arr[i].to);
            sum+=arr[i].len;
            if(cnt==n-1)
            {
                break;
            }
        }    
    }
    cout<<sum<<endl;
} 
return 0;

}

第二道：连线问题

问题描述

4.24

include <iostream>

include <algorithm>

include <cmath>

using namespace std;
const int maxn = 1e6+5;
int fa[maxn];
int x[maxn];
int y[maxn];
void init()
{

for(int i=1;i<maxn;++i)
{
    fa[i]=i;
}

}
int find(int x)
{

if(x==fa[x])
{
    return x;
}    
return fa[x] = find(fa[x]);

}
void merge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    fa[p]=q;
}

}
bool judge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    return true;
}
return false;

}
struct node
{

int from;
int to;
double len;

}arr[10005];
bool cmp(node a,node b)
{

return a.len<b.len;

}
int main()
{

int n;
cin>>n;
for(int i=0;i<n;++i)
{
    cin>>x[i]>>y[i];
}
int top=0;
for(int i=0;i<n;++i)
{
    for(int j=0;j<n;++j)
    {
        if(i!=j)
        {
            double dist = sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
            int from = x[i]*100+y[i];
            int to = x[j]*100+y[j];
            arr[top].from = from;
            arr[top].to = to;
            arr[top++].len = dist;    
        }
    }
}
sort(arr,arr+top,cmp);
init();
double sum = 0;
int cnt = 0;
for(int i=0;i<top;++i)
{
    if(judge(arr[i].from,arr[i].to))
    {
        merge(arr[i].from,arr[i].to);
        cnt++;
        sum+=arr[i].len;
        if(cnt==n-1)
        {
            break;
        }
    }    
}
//cout<<sum<<endl;
printf("%.2lf\n",sum);
return 0;

}

第三道：穿越雷区

问题描述

256

include <iostream>

include <algorithm>

include <cmath>

using namespace std;
const int maxn = 3e4+5;
int fa[maxn];
void init()
{

for(int i=1;i<maxn;++i)
{
    fa[i]=i;
}

}
int find(int x)
{

if(x==fa[x])
{
    return x;
}    
return fa[x] = find(fa[x]);

}
void merge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    fa[p]=q;
}

}
bool judge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    return true;
}
return false;

}
struct node
{

int from;
int to;
double len;

}arr[50005];
bool cmp(node a,node b)
{

return a.len<b.len;

}
int main()
{

int n,m;
while(cin>>n>>m)
{
    int a,b,len;
    for(int i=0;i<m;++i)
    {
        cin>>arr[i].from>>arr[i].to>>arr[i].len;
    }
    sort(arr,arr+m,cmp);
    init();
    int sum = 0;
    int cnt=0;
    for(int i=0;i<m;++i)
    {
        if(judge(arr[i].from,arr[i].to))
        {
            merge(arr[i].from,arr[i].to);
            sum+=arr[i].len;
            cnt++;
            if(cnt==n-1)
            {
                break;
            }    
        }
    }
    cout<<sum<<endl;
}
return 0;

}

第四道：高速公路

问题描述

include <iostream>

include <algorithm>

include <cmath>

using namespace std;
const int maxn = 3e4+5;
int fa[maxn];
void init()
{

for(int i=1;i<maxn;++i)
{
    fa[i]=i;
}

}
int find(int x)
{

if(x==fa[x])
{
    return x;
}    
return fa[x] = find(fa[x]);

}
void merge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    fa[p]=q;
}

}
bool judge(int x,int y)
{

int p = find(x);
int q = find(y);
if(p!=q)
{
    return true;
}
return false;

}
struct node
{

int from;
int to;
int len;

}arr[10005];
bool cmp(node a,node b)
{

return a.len<b.len;

}
int main()
{

int n,m;
while(cin>>n>>m)
{
    int a,b,len;
    for(int i=0;i<m;++i)
    {
        cin>>arr[i].from>>arr[i].to>>arr[i].len;
    }
    sort(arr,arr+m,cmp);
    int ans = 1<<30;
    for(int i=0;i<m;++i)
    {
        int min_val = 1<<30;
        int max_val = -1<<30;
        int cnt=0;
        init();
        for(int j=i;j<m;++j)
        {
            if(judge(arr[j].from,arr[j].to))
            {
                merge(arr[j].from,arr[j].to);
                min_val = min(min_val,arr[j].len);
                max_val = max(max_val,arr[j].len);
                cnt++;    
            }    
        }
        if(cnt!=n-1)
        {
            continue;
        }
        else 
        {
            ans = min(ans,(max_val-min_val));    
        }
    }
    if(ans ==  1<<30)
    {
        cout<<"-1"<<endl;
    }
    else 
    {
        cout<<ans<<endl;
    }
}
return 0;

}

Prim最小生成树算法

Prim算法对于使用邻接矩阵表示的图来说非常方便实现，所以在求稀疏图的最小生成树的时候常用Prim算法。

模板

#define INF 0x1f1f1f1f    //定义一个整数常量，表示无穷大
// prim函数返回得到的最小生成树的n-1条边的权值和
// 参数cost 为表示图的矩阵，n为顶点个数
int prim(int cost[][200],int n)
{
    //low表示每个点到生成树的最小距离，vis表示一个点是否已经加入生成树中
    int low[10000],vis[10000]=0;        //顶点数n<10000 
    int i,j,p;
    int min,res=0;                        //res表示最小生成树权值和 
    vis[0]=1;                            //将第一个顶点加入集合S 
    for(int i=1;i<n;++i)                //并更新该顶点到其他顶点的距离 
    {
        low[i] = cost[0][i];
    }
    for(int i=1;i<n;++i)                //尝试加入剩下的n-1条边 
    {
        min = INF;                        //寻找点集V-S中距离集合S最近的距离的点 
        p=-1;                            //min为权值，p为位置 
        for(int j=0;j<n;++j)
        {
            if(0==vis[j] && min>low[j])
            {
                min = low[j];
                p = j;
            }
        }    
        //min==INF 说明找不到能够加入的点了，说明图是不连通的（已经加入的点集和未加入的点集不连通）。
        if(min==INF) return -1;
        
        res+=min;
        vis[p]=1;        //P点加入生成树的点集 
        
        for(j=0;j<n;++j)    //加入该点后更新集合S到集合V-S之间的距离 
        {
            if(vis[j]==0 && low[j]>cost[p][j])
            {
                low[j] = cost[p][j];    
            }    
        } 
    }
    return res;    
}

第一道：hdu

题目描述：

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

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.

#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x1f1f1f1f    //定义一个整数常量，表示无穷大
// prim函数返回得到的最小生成树的n-1条边的权值和
// 参数cost 为表示图的矩阵，n为顶点个数
int prim(int cost[][100],int n)
{
    //low表示每个点到生成树的最小距离，vis表示一个点是否已经加入生成树中
    int low[10000];
    int vis[10000]={0};        //顶点数n<10000 
    int i,j,p;
    int min,res=0;                        //res表示最小生成树权值和 
    vis[0]=1;                            //将第一个顶点加入集合S 
    for(int i=1;i<n;++i)                //并更新该顶点到其他顶点的距离 
    {
        low[i] = cost[0][i];
    }
    for(int i=1;i<n;++i)                //尝试加入剩下的n-1条边 
    {
        min = INF;                        //寻找点集V-S中距离集合S最近的距离的点 
        p=-1;                            //min为权值，p为位置 
        for(int j=0;j<n;++j)
        {
            if(0==vis[j] && min>low[j])
            {
                min = low[j];
                p = j;
            }
        }    
        //min==INF 说明找不到能够加入的点了，说明图是不连通的（已经加入的点集和未加入的点集不连通）。
        if(min==INF) return -1;
        
        res+=min;
        vis[p]=1;        //P点加入生成树的点集 
        
        for(j=0;j<n;++j)    //加入该点后更新集合S到集合V-S之间的距离 
        {
            if(vis[j]==0 && low[j]>cost[p][j])
            {
                low[j] = cost[p][j];    
            }    
        } 
    }
    return res;    
} 
int main()
{
    int a[100][100];
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                cin>>a[i][j];    
            }    
        }    
        int t,x,y;
        cin>>t;
        while(t--)
        {
            cin>>x>>y;
            a[x-1][y-1]=a[y-1][x-1]=0;
        }
        int ans = prim(a,n);
        cout<<ans<<endl;
    }
    return 0;    
}

最小生成树

最小生成树的应用

kruskal最小生成树算法

思路

演示

四道模板题：

第一道：布设光纤

include<iostream>

include<algorithm>

第二道：连线问题

include <iostream>

include <algorithm>

include <cmath>

第三道：穿越雷区

include <iostream>

include <algorithm>

include <cmath>

第四道：高速公路

include <iostream>

include <algorithm>

include <cmath>

Prim最小生成树算法

模板

第一道：hdu