最小生成树Boruvka算法

prim o （n2） o（m lgn）
克鲁斯卡尔 o mlgm

Boruvka 最坏（n+m）lg n （常用于完全图）

我们每次 将已加入生成树的 点和 未加入生成树的 点划分为两个集合

每次找 两个集合内部 能连接的 最小值

然后进行标记

pair比较的时候 不能{ } 必须make_pair 以前不知道

#include 
using namespace  std;
//#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1<<62
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int n, m , k;
bool f;
array<int, 3>e[N];
int fa[N];
pii mp[N];
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int bor() {
	int res = 0;
	f = 1;
	int cnt = 0;
	fer(i, 1, n)fa[i] = i;
	while(cnt < n - 1) {
		int idx = 0;
		fer(i, 1, n)mp[find(i)] = {1 << 30, 1 << 30};
		fer(i, 1, m) {
			int x = find(e[i][0]);
			int y = find(e[i][1]);
			if(x == y)continue;
			idx++;
			mp[x] = min(mp[x], make_pair( e[i][2], i) );
			mp[y] = min(mp[y], make_pair( e[i][2], i)) ;
		}
		if(!idx)break;
		fer(i, 1, m) {
			int x = find(e[i][0]);
			int y = find(e[i][1]);
			if(x == y)continue;
			if(mp[x] == make_pair( e[i][2], i ) || mp[y] == make_pair( e[i][2], i) ) {
				fa[x] = y;
				res += e[i][2];
				cnt++;
			}
		}
	}
	if(cnt < n - 1)f = 0;
	return res;
}
void solve() {
	cin >> n >> m;
	fer(i, 1, m) {
		cin >> e[i][0] >> e[i][1] >> e[i][2];
	}
	cout << bor();

}
int main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
}


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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include 
using namespace  std;
//#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1<<62
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int n, m , k;
bool f;
array<int, 3>e[N];
int fa[N];
int mp[N];
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int ne[N];
int bor() {
	int res = 0;
	f = 1;
	int cnt = 0;
	fer(i, 1, n)fa[i] = i;
	while(1) {
		int idx = 0;
		fer(i, 1, n)mp[i] = 1<<30;
		fer(i, 1, m) {
			int x = find(e[i][0]);
			int y = find(e[i][1]);
			if(x == y)continue;
            if(e[i][2]<mp[x]) mp[x]=e[i][2],ne[x]=y;
            if(e[i][2]<mp[y]) mp[y]=e[i][2],ne[y]=x;
		}
		fer(i,1,n){
            if(mp[i]<(1<<30)&& find(i)!=find(ne[i])){
                fa[find(i)]=find(ne[i]);
                f=1;
                idx++;
                res+=mp[i];
            }
        }
        if(!idx)break;
	}
	return res;
}
void solve() {
	cin >> n >> m;
	fer(i, 1, m) {
		cin >> e[i][0] >> e[i][1] >> e[i][2];
	}
	cout << bor();

}
int main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
}


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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74