不是VIP会员,不能显示答案

题目解答

题目:
#include<bits/stdc++.h>

const int N=1e6+50;

int n, m, min[N],out[N],f[N],siz[N],ans;



struct edge

{

int u, v, w;

} e[N];



inline int find(int x)

{

while (x!=f[x])

x=f[x]=f[f[x]];

return x;

}



inline void merge(int x,int y)

{

if (siz[x]>siz[y]) std::swap(x,y);

f[x]=y;

}



int main()

{

scanf ("%d%d", &n, &m);

for (int i=1; i<=n; ++i)

{

f[i]=i,siz[i]=1;

}

for (int i=1; i<=m; ++i)

{

scanf ("%d%d%d", &e[i].u,&e[i].v,&e[i].w);

}

int components=n;

while (components>1)

{

memset (min,0x3f,sizeof (min));

for (int i=1; i<=m; ++i)

{

int u=find(e[i].u),v=find(e[i].v),w=e[i].w;

if (u!=v)

{

if (w<min[u]) min[u]=w,out[u]=v;

if (w<min[v]) min[v]=w,out[v]=u;

}

}

for (int i=1; i<=n; ++i)

{

int x=find(i) ;

if (out[x])

{

int y=find(out[x]);

if (x!=y)

{

merge(x,y);

--components;

ans+=min[x];

}

}

}

}

printf("%d",ans);

return 0;

}




提示:该程序的输入为一张n个点m条边的连通无向图。输入格式为:

输入的第一行包含两个整数 n,m(1≤n≤m≤100)。

接下来一行,包含三个整数u,v,w(1≤u,v≤n,1≤w≤100)。





判断题

1) (1分)该程序实现了用于求无向图G=(V,E)的最小生成树的算法。( )

2) (1分)程序中使用了邻接矩阵来存储图G=(V,E)。( )

3) 为了确保该算法的结果符合预期输入需要保证所有的w互不相同。( )

4) 对于任意合法的输入,该程序一定会在有限步内返回结果。( )


选择题

5) 变量components在运行过程中可达到的最小值为( )。

6) 该程序的时间复杂度为( ) 。
考点:
分析:
解答:
评论:
老师: