tc is coming,上周的考试真是难受啊！！！！！！！
sad，可是还是要好好学算法啊！！！
讲道理，我感觉那些博客画那些图还有点看不懂，还是直接说比较好。。。。
他要求的其实就是n个点连起来最短的距离。基本可以这么理解。他最重要的一点就是先将个点到各点的距离从小到大排序，然后取最小的就是，这样就 可以取到最小值了！！！！！
然后怎么判断有没有重复？那就是并查集来判断有没有在同根了。
下面上提目：
code:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
struct wtc {
int from,to;
ll len;
};
wtc tc[500100];
int pa[210000],ran[210000];
bool judge(wtc a,wtc b) {
return a.len < b.len;
}
int find(int a) {
return a == pa[a] ? a : pa[a] = find(pa[a]);
}
void unite(int a,int b) {
int x = find(a);
int y = find(b);
if(x!=y) {
if(ran[x] > ran[y]) pa[y] = x;
else {
pa[x] = y;
if(x == y) ran[x]++;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin>>n>>m;
int i = 0;
for(; i < m; i++) cin>>tc[i].from >> tc[i].to >> tc[i].len;
sort(tc,tc + m,judge);
for(i = 1; i <= n; i++) pa[i] = i;
int k = 1;
ll total = 0;
for(i = 0; i < m; i++) {
if(k == n) break;
if(pa[tc[i].from] != pa[tc[i].to]) {
total += tc[i].len;
unite(tc[i].from,tc[i].to);
k++;
}
}
cout<<total;
return 0;
}
能不能用二维数组或者一个bool数组判断是否有遍历过？答案是不行的。因为数组和bool只能判断是否用过，这样可能会忽略掉一些东西。比如
1 2 1
3 4 1
2 3 1
这样的一组数据用bool或者数组存的话只会加上前两种的长度，不会加上第三个，各样他们就不能连在一起了。并查集则可以将他们连在一起，已经连接过的便不再连接，又因为这里的数组是用sort拍过序的，所以取得就是最小值。