A: 树学家丁丁妹
题目描述
为了响应国家“退耕还林”的号召，丁丁妹正在将她的大头菜田改造成树林。
然而这和这道题并没有什么关系。
重要的是，丁丁妹思考了如下一个问题：
给定一个有n 个点m 条边的无向图，每条边有一个边权c 。
如何选择n−1 条边来让这个无向图连通，并且使得这n−1条边的边权之和最小呢？
显然这个问题对于丁丁妹来说太困难了，于是她又花重金聘请了你，希望你来解决这个问题。
输入描述
单组数据，第一行为两个正整数n,m 。
接下来m 行，每行有三个正整数x,y,c ，表示x 号点和y号点之间存在一条边权为c 的无向边。
数据保证：
1. 对于80% 的数据， 1 ≤ n,m ≤ 1000
2. 对于100% 的数据，1≤n,m≤1000000
3. 对于100% 的数据， 1 ≤ c ≤ 100
输出描述
一个整数 c ，代表边权之和的最小值；若无法选择n−1条边让图连通，输出− 1 。
样例输入
3 3
1 2 1
1 3 2
2 3 3
样例输出
3
思路:
这个题一看数据量 1e6 这么大,指定不能用二维数组,所以最短路或者dp直接求实在是行不通,
问的是联通图, 最短连通路径,又需要压缩空间来优化, 很容易就想到并查集
另外, 注意这里说的连通路径不是那种"一笔画的"欧拉路, 而是 ------- 连通的可交叉的路径-------类似一棵树
实际上---------最小生成树------------就是我们要求的连通路径
问题在于怎么使用并查集来表示一条完整的,"从1-n都能连通的路径",另外每条路径都该怎么算出来
并查集来表示存在的连通关系, 我们知道 find()函数就是为了 将所有连通的节点归到同一个"根"上面,
这样可以形成一个"同根树",如果发现所有的节点都只有一个根, 说明这个图是联通的,
最小生成树的求解-----Kruskal算法/Prim算法-----实际上就是贪心!!!
这里用Kruskal , 我们把所有的边排序,每次操作,
- 检查是否加入新边,是否和已有边连通冲撞
- 是则加入, 并且更新节点的根(合并)
最后只检查新边是否和成环,最后检查是否所有的点都连通,检查边的数目是否为n-1即可
注意合并是怎样的,比如
6 和 4
1 3 5 2 7
存在5,2 之间有一条边, 显然不是5-2合并,因为这样就会有两个根了, 检测连通靠的是根是否相同,
所以, 另一棵树的根, 也就是6 ,接到另一棵树,
至于怎么接, 这里看需要, 如果保持结构的话, 就要以5为根旋转成,
5 类似于平衡树, 6的爸爸变成5, 然后 5 的爸爸变成2,这样就保持了原来的结构性质
6
1 3
如果需要彻底压缩,尽量优化查找时间,那就让, 6, 1, 3, 5 的爸爸变成 4
假如不要求时间和效率, 我们只要求联通路径长, 简单合并就可以了
----比如, 6---右边的爸爸-------变成--------左边的爸爸-------2也可以得到确结果,如下代码, 但是会TE
1 int l=find(x[i].l); 2 int r=find(x[i].r); 3 f(r!=l) { 4 k++; 5 ans+=x[i].d; 6 f[r]=x[i].l; 7 }
改成了把6的爸爸变成4, 还是TE,6---右边的爸爸-------变成--------左边的爸爸-------2
1 if(r!=l) { 2 k++; 3 ans+=x[i].d; 4 f[r]=l; 5 }
原因在于没有固定好一个策略合并, "右边的合并到左边的"并不是一个有序的策略,
因为节点是有序号的, 但是, 输入的时候并没有规定大的节点一定在右边
也不能保证, 比如大的节点合并到小的那里去,
所以加个判断条件,改成这样就过了
1 if(r!=l) { 2 k++; 3 ans+=x[i].d; 4 if(r>l)f[r]=l; 5 else f[l]=r; 6 }
完整代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 const int M=1000000+10; 8 int n,m; 9 struct D { 10 int l,r; 11 int d; 12 D() { 13 l=0,r=0,d=0; 14 } 15 } x[M]; 16 int f[M]; 17 void init() { 18 for(int i=1; i<=n; i++) { 19 f[i]=i; 20 } 21 } 22 int find(int t) { 23 return f[t]==t?t:find(f[t]); 24 } 25 /* 26 int find(int t1) { 27 int t=t1; 28 while(f[t]!=t) { 29 t=f[t]; 30 } 31 return t; 32 } 33 */ 34 bool cmp(D a,D b) { 35 return a.d<b.d; 36 } 37 int main () { 38 memset(x,0,sizeof(x)); 39 scanf("%d%d",&n,&m); 40 init(); 41 ll ans=0; 42 for(int i=1; i<=m; i++) { 43 int l,r; 44 scanf("%d%d%d",&x[i].l,&x[i].r,&x[i].d); 45 } 46 sort(x+1,x+1+m,cmp); 47 int k=0; 48 bool t=0; 49 for(int i=1; i<=m; i++) { 50 int l=find(x[i].l); 51 int r=find(x[i].r); 52 if(r!=l) { 53 k++; 54 ans+=x[i].d; 55 if(r>l)f[r]=l; 56 else f[l]=r; 57 } 58 if(k==n-1) { 59 t=1; 60 break; 61 } 62 } 63 if(t==0)cout<<"-1"; 64 else printf("%lld",ans); 65 cout<<" "; 66 return 0; 67 }