【NOJ1596、1597】【贪心算法之最小生成树】最少修建多长的公路能把所有村庄连起来(图示Prim与Kruskal算法)
1596.最少修建多长的公路能把所有村庄连起来(一)
时限:1000ms 内存限制:10000K 总时限:3000ms
描述
一个地区有n个村庄,有一些村子之间可以修路,已知每条路的长度,问最少修建多长的公路可以把所有的村子连接起来。
输入
先输入两个正整数n,m(n小于10000,m小于100000),表示有n个村庄,m条可以修建的路,接下来的m行每行三个整数,前两个表示村庄的编号(0~n-1),第三个表示这条路的长度。
输出
输出路的总长度的最小值。
#include <iostream>
#include <climits>
using namespace std;
//本题选用Kruskal算法,因邻接矩阵顶点太多,边太少
//若用二维数组存放数据太浪费
//本题采用并查集判断两个顶点是否连通
int n,m;
int a[10000]; //并查集
int x[100000],y[100000],dis[100000]; //存放边
int isIn[100000]; //边是否已在集合中
int fsearch(int x); //返回并查集中x节点的根节点
void a_add(int x, int y); //将两个顶点连通
bool isUn(int x, int y); //判断x和y两个顶点是否连通
int main()
{
//Krustal算法+并查集
//输入数据
cin>>n>>m;
for(int i=0; i<m; i++)
{
cin>>x[i]>>y[i]>>dis[i];
}
//初始化
for(int i=0; i<n; i++)
{
a[i]=i;
}
//将边按权值升序排列
for(int i=0; i<m; i++)
{
for(int j=i; j<m; j++)
{
if(dis[j]<dis[i])
{
swap(dis[j],dis[i]);
swap(y[j],y[i]);
swap(x[j],x[i]);
}
}
}
//按升序遍历边,加入集合,共m条边
int dist=0;
for(int i=0; i<m; i++)
{
if(!isUn(x[i],y[i]))//若第i条边的两个顶点不连通
{
a_add(x[i],y[i]); //将两个顶点连通
dist+=dis[i]; //加入这条边的边长
}
else //若已经连通则查看下一条边
{
continue;
}
}
cout<<dist<<endl;
return 0;
}
int fsearch(int x) //返回并查集中x节点的根节点
{
int f=a[x];
while(f!=a[f])
{
f=a[f];
}
a[x]=f;
return f;
}
void a_add(int x, int y) //将两个顶点连通
{
int kx=fsearch(x);
int ky=fsearch(y);
a[ky]=kx;
}
bool isUn(int x, int y) //判断x和y两个顶点是否连通
{
int kx=fsearch(x);
int ky=fsearch(y);
if(kx==ky)
{
return true;
}
else
{
return false;
}
}
1597.最少修建多长的公路能把所有村庄连起来(二)
时限:1000ms 内存限制:10000K 总时限:3000ms
描述
一个地区有n个村庄,有一些村子之间可以修路,已知每条路的长度,问最少修建多长的公路可以把所有的村子连接起来。
输入
先输入一个正整数n(n小于500),表示有n个村庄,接下来n行每行n个正整数,其中第i行第j列的元素表示第i个村庄到第j个村庄之间的距离。
输出
输出路的总长度的最小值。
#include <iostream>
#include <climits>
using namespace std;
//本题选用Prim算法,因邻接矩阵不稀疏
int n,m;
int dist[500][500]; //邻接矩阵
int isIn[10000]; //节点是否在集合中
int f[10000]; //权值:每个节点到集合的距离
int mindist(); //返回当前离集合最近点的下标
int main()
{
//Prim算法
cin>>n;
for(int i=0; i<n; i++) //输入数据
{
for(int j=0; j<n; j++)
{
cin>>dist[i][j];
}
}
//初始化isIn数组
isIn[0]=1; //将节点0加入集合
for(int i=1; i<n; i++)
{
isIn[i]=0;
}
//初始化各节点权值
for(int i=1; i<n; i++)
{
f[i]=dist[0][i]; //初始权值为到顶点i的距离
}
int dis=0; //总距离
for(int cnt=1; cnt<n; cnt++) //每次for循环添加一个节点进集合
{
int x=mindist(); //返回离集合最近节点下标
//cout<<x<<' '<<isIn[x]<<endl;
isIn[x]=1; //将该节点加入集合
dis+=f[x]; //将权值加入总距离中
//cout<<dis<<' ';
for(int i=0; i<n; i++) //更新各节点权值
{
if(!isIn[i]) //遍历不在集合中的节点
{
if(dist[x][i]<f[i])
{
f[i]=dist[x][i];
//cout<<f[i]<<endl;
}
}
}
}
cout<<dis<<endl;
return 0;
}
int mindist() //返回当前离集合最近点的下标
{
int min_i=1;
int min_dist=INT_MAX;
for(int i=1; i<n; i++)
{
if(!isIn[i])
{
if(f[i]<min_dist)
{
min_dist=f[i];
min_i=i;
}
}
}
return min_i;
}
【后记】
1.最小生成树问题,有两种算法,Prim算法与Krustal算法
当e=Ω(n²)时,Prim算法性能好
当e=o(n²)时,Krustal性能好
2.Prim算法将顶点分为两个集合A和B,集合A中最初只有顶点0,其余顶点都在集合B中
集合B中每个顶点都有一个权值 f,f [ i ] 定义为“顶点 i 到集合A的最短距离”,初始值为“顶点 i 到顶点0的最短距离”
若顶点 i 到顶点0没有连接边,那么 f [ i ] 的初始值为INT_MAX,即无穷大,需要#include <climits>
开始for循环,每次循环,从集合B中选取一个权值最小的顶点X加入集合A,相当于顶点X已经与集合A中的各顶点连通,然后更新集合B中剩下的顶点权值
更新意义在于:顶点X已经从集合B加入了集合A,那么如果集合B中有一个顶点Y到顶点X的距离比它到集合A的距离更短,就要把顶点Y的权值更新成它到顶点X的距离
当for循环次数等于顶点数-1时,每个顶点都被加入了集合A,意味着所有顶点都连通起来
3.Kruskal算法,先将各条边按照距离值从小到大排列
开始for循环,每次循环选取一条距离值最小的边,判断一下这条边两端的顶点A和顶点B是否连通
如果A和B不连通,就把它们连通起来,确定添加这条边
如果A和B连通,就删除这条边不添加(否则会形成回路),查看下一条边
当循环次数等于边数时,所有边都被查看了一遍,要么添加要么删除,最后所有顶点都连通起来,并且没有回路
4.在Kruskal算法中,需要判断一条边的两个顶点是否连通,这里用到了并查集
并查集可以用一个数组a[]表示,a [ i ] = i 表示节点 i 为根节点
若一条边的顶点A和顶点B的根节点相同,说明两个顶点在一棵树上,即连通
若顶点A和顶点B的根节点不同,说明不连通,那么在Kruskal算法中需要让A和B连通,此时只需求A的根节点root(A),B的根节点root(B),令a[ root(A) ] = root(B)就可以,具体代码如下:
for(int i=0; i<n; i++) //初始化并查集
{
a[i]=i; //每个节点都是自己的根节点
}
int fsearch(int x) //返回并查集中x节点的根节点
{
int f=a[x];
while(f!=a[f]) //只有a[f]==f时,f才是根节点
{
f=a[f];
}
a[x]=f; //更新x的根节点,让其直接指向f
return f;
}
void a_add(int x, int y) //将两个顶点连通
{
int kx=fsearch(x); //x的根节点
int ky=fsearch(y); //y的根节点
a[ky]=kx; //让ky的根节点变成kx
}