胡队长带领HA实验的战士们玩真人CS,真人CS的地图由一些据点组成,现在胡队长已经占领了
n个据点,为了方便,将他们编号为1-n,为了隐蔽,胡队长命令战士们在每个据点出挖一个坑,让战士们躲在坑里。由于需要在任意两个点之间传递信息,两个坑之间必须挖出至少一条通路,而挖沟是一件很麻烦的差事,所以胡队长希望挖出数量尽可能少的沟,使得任意两个据点之间有至少一条通路,顺便,尽可能的∑d[i][j]使最小(其中d[i][j]为据点i到j的距离)。
第一行有2个正整数n,m,m表示可供挖的沟数。 接下来m行,每行3个数a,b,v,每行描述一条可供挖的沟,该沟可以使a与b连通,长度为v。
输出一行,一个正整数,表示要使得任意两个据点之间有一条通路,至少需要挖长的沟。(数据保证有解)
输入
2
2 1 2
1 1 2 3
输出
1
输入
3 3
1 2 3
2 3 4
1 3 5
输出
7
对于100%的测试数据:
1 ≤ n ≤ 100000
1 ≤ m ≤ 500000
1 ≤ v ≤ 10000链接:https://ac.nowcoder.com/acm/problem/17509
来源:牛客网
#include
#include
#include
#include
using namespace std;
#define INF 10e7
typedef struct edge{
int v,u,len;
}EDGE;
EDGE edge[500005];
int pa[100005];
int cnt=0;
void init(int n)
{
for(int i=1;i<=n;i++){
pa[i]=i;
}
}
bool cmp(EDGE a,EDGE b)
{
return a.len<b.len;
}
void addEdge(int v,int u,int len)
{
edge[++cnt].v=v;
edge[cnt].u=u;
edge[cnt].len=len;
}
int find(int a)
{
if(pa[a] == a)
{
return a;
}
else
{
return pa[a]=find(pa[a]);
}
}
int Union(int a,int b)
{
if(find(a) != find(b)){
pa[find(a)]=b;
return 1;
}
return 0;
}
int main()
{
int n,m,a,b,v;
scanf("%d%d",&n,&m);
init(n);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&v);
addEdge(a,b,v);
}
sort(edge + 1, edge + m + 1,cmp);
//quickSort(1,m);
int ans=0;
for(int i=1;i<=m;i++){
if(Union(edge[i].v,edge[i].u)){
ans+=edge[i].len;
}
}
printf("%d\n",ans);
}
用的方法是kruskal算法+并查集,起初这道题想着用prim算法的,用链式前向星去存储路径节点,然后prim算法求出最短路径,但是总是超时,后来看了一下,应为他给出的用例两点之间会有重复的路径,于是将其优化,只保留最短的路径,但是还是不行。后来看了题解是使用kruskal算法,算法的局限性就出来了,kruskal适合处理邻接表,时间复杂度和把所有边排序的复杂度一样,为O(mlogm)。而prim算法适合处理邻接矩阵,时间复杂度为O(n2),n为结点数,m为边。而题目给出的结点数量范围为100000,这样的范围使用邻接矩阵处理显然内存会爆掉,即使使用邻接表存,然后使用prim算法处理,时间上也很复杂。
这道题,把所有路径存储,然后按照边从小到大排序,然后就是找到最短边,并查集查看是否连通,如果已经连通了则不能添加,如果不连通则添加到集中并加上路径长度。