Boruvka生成树算法

(Updated: )
(11 mins to read)

核心:每次从所有当前的连通块向其他连通块扩展出最小边,直至剩下一个连通块每进行一次操作,连通块数量减半 $O(m\log n)$ 取决于计算最小边的代价

codechef spanning tree

交互题,每次可以给出两个点集A,B进行询问,会返回两个集合间的最小边,要求询问的$\sum |A|<=1e4, \sum |A|+|B|<=2e6,n<=1e3$,最后输出该图的最小生成树的权值和按照上述算法询问即可

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
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e3 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, fa[N], idx[N], mncost;
pii mn[N];
vector<int> scc[N];
bool vis[N];
int find(int x)
{
  if(x==fa[x]) return x;
  return fa[x] = find(fa[x]);
}
bool merge(int u, int v)
{
  u = find(u), v = find(v);
  if(u!=v)
  {
    fa[u] = v;
    return true;
  }
  return false;
}
pii ask(vector<int> &a)
{
  for(int i=1; i<=n; i++) vis[i] = 0;
  cout << 1 << ' ' << sz(a) << ' ' << n-sz(a) << endl;
  for(int x : a)
  {
    cout << x << ' ';
    vis[x] = 1;
  }
  cout << endl;
  for(int i=1; i<=n; i++) if(!vis[i]) cout << i << ' ';
  cout << endl;
  int u, v, w; cin >> u >> v >> w;
  return mp(v, w);
}
int main()
{
  cin >> n;
  for(int i=1; i<=n; i++) fa[i] = i;
  while(true)
  {
    int cnt = 0;
    for(int i=1; i<=n; i++)
      if(fa[i]==i) idx[i] = ++cnt;
    if(cnt==1) break;
    for(int i=1; i<=n; i++)
      scc[idx[find(i)]].pb(i);
    for(int i=1; i<=cnt; i++) mn[i] = {-1, 0};
    for(int i=1; i<=cnt; i++)
    {
      auto cur = ask(scc[i]);
      if(mn[i].fi==-1) mn[i] = {cur.se, cur.fi};
      else if(cur.se<mn[i].fi) mn[i] = {cur.se, cur.fi};
      scc[i].clear();
    }
    for(int i=1; i<=n; i++)
      if(fa[i]==i && merge(i, mn[idx[i]].se))
        mncost += mn[idx[i]].fi;
  }
  cout << 2 << ' ' << mncost << endl;
  return 0;
}

cf888G xormst

一张完全图,点数2e5,每个点有点权$a_i$​,边$(i,j)$的权值为$a_i xor a_j$​,求该图的mst思考如何求出当前集合与其他集合的最小边权:建出01trie,每次把该集合的点权删除,然后逐个询问与该点权xor后的最小值取小,最后再插入还原即可

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, a[N];
int fa[N], idx[N], cnt, mnto[N], mnval[N];
vector<int> scc[N];
int find(int x)
{
  if(x==fa[x]) return x;
  return fa[x] = find(fa[x]);
}
bool merge(int u, int v)
{
  u = find(u), v = find(v);
  if(u!=v)
  {
    fa[u] = v;
    return true;
  }
  return false;
}
int tot, nxt[N*29][2], sz[N*29][2], id[N*29];
void upd(int x, int v, int idx)
{
  int now = 0;
  for(int i=29; i>=0; i--)
  {
    int k = (x>>i)&1;
    if(!nxt[now][k]) nxt[now][k] = ++tot;
    sz[now][k] += v;
    now = nxt[now][k];
  }
  if(v==1) id[now] = idx;
}
pii ask(int x)
{
  int ans = 0, now = 0;
  for(int i=29; i>=0; i--)
  {
    int k = (x>>i)&1;
    if(sz[now][k]) now = nxt[now][k];
    else now = nxt[now][k^1], ans |= (1<<i);
  }
  return {ans, id[now]};
}
int main()
{
  double startTime = (double)clock();
  //mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  scanf("%d", &n);
  //n = 2e5;
  for(int i=1; i<=n; i++)
  {
    fa[i] = i;
    scanf("%d", a+i);
    //a[i] = abs(rnd()%(1<<30));
  }
  sort(a+1, a+n+1);
  n = unique(a+1, a+n+1) - a - 1;
  for(int i=1; i<=n; i++) upd(a[i], 1, i);
  ll ans = 0;
  while(true)
  {
    cnt = 0;
    for(int i=1; i<=n; i++)
      if(fa[i]==i)
      {
        idx[i] = ++cnt;
        mnto[cnt] = mnval[cnt] = -1;
      }
    //debug(cnt);
    if(cnt==1) break;
    for(int i=1; i<=n; i++)
      scc[idx[find(i)]].pb(i);
    for(int i=1; i<=cnt; i++)
    {
      for(int x : scc[i]) upd(a[x], -1, x);
      for(int x : scc[i])
      {
        auto cur = ask(a[x]);
        if(mnto[i]==-1)
        {
          mnval[i] = cur.fi;
          mnto[i] = cur.se;
        }
        else if(cur.fi<mnval[i])
        {
          mnval[i] = cur.fi;
          mnto[i] = cur.se;
        }
      }
      for(int x : scc[i]) upd(a[x], 1, x);
      scc[i].clear();
    }
    for(int i=1; i<=n; i++)
      if(fa[i]==i && merge(i, mnto[idx[i]]))
        ans += mnval[idx[i]];
  }
  printf("%lld\n", ans);
  cerr << ((double)clock() - startTime) / CLOCKS_PER_SEC << endl;
  return 0;
}