|
楼主 |
发表于 2018-2-13 11:40:41
|
显示全部楼层
先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有 n-1 条边为止。
时间复杂度为为O(e^2), 使用并查集优化后复杂度为 O(eloge),与网中的边数有关,适用于求边稀疏的网的最小生成树。
- #include<cstdio>
- #include<algorithm>
- #define N 101
- using namespace std;
- int tr[N];
- int findroot(int x)
- {
- if(tr[x]==-1)
- return x;
- else
- {
- int tmp=findroot(tr[x]);
- tr[x]=tmp;
- return tmp;
- }
- }
- struct Edge
- {
- int a,b;
- int cost;
- bool operator < (const Edge &A) const
- {
- return cost<A.cost;
- }
- }edge[6000];
- int main()
- {
- int n;
- while(scanf("%d",&n)!=EOF&&n!=0)
- {
- int num=n*(n-1)/2;
- for(int i=1;i<=num;i++)
- scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);
- sort(edge+1,edge+num+1);
- for(int i=0;i<=N;i++)
- tr[i]=-1;
- int ans=0;
- for(int i=1;i<=n;i++)
- {
- int a,b;
- a=findroot(edge[i].a);
- b=findroot(edge[i].b);
- if(a!=b)
- {
- tr[b]=a;
- ans+=edge[i].cost;
- }
- }
- printf("%d\n",ans);
- }
- return 0;
- }
复制代码 |
|