UOJ 176新年の繁栄

タイトルリンク

Boruvka生成ツリーアルゴリズム

(Boruvka)アルゴリズムは,まず各点を1つの結合ブロックと見なし,その後,結合ブロック間で最適なエッジを絶えず探して結合する.なぜなら、各インターフェースブロックの数は少なくとも半分に縮小されるからである.だからマージ回数は(log)の先にすべてのポイント権を(trie)ツリーに掛けます.次に、各インターフェースブロックをマージするとき.コネクトブロックの各ポイントについて、彼が見つけられる最も優れたエッジを検索します.すなわち,現在位置が(1)であれば1サブツリーを検索し,そうでなければ0サブツリーも1サブツリーも検索する.このような1本の木は必ず捜しなければならない.したがって,0サブツリーを1サブツリーと0サブツリーを統合した結果とする.そして検索できます.もう一つの問題は.もし現在のサブツリーのすべての点がこのインターフェースブロックに入っていたらどうしますか.したがって、各ツリーにおける連結ブロック番号の最大値と最小値が統計される.そして、現在のサブツリーにこの連結ブロックに属していない点があるかどうかを知ることができます.連結ブロックを連結した後、各点が連結された連結ブロックの中の点が属する連結ブロックを修正すればよい.複雑度(O((n+2^m)mlogn))

より優れたアプローチ

上の方法はコードが長く、構想が複雑です.もっと良い方法があります.まず、すべての重み値が同じ点を1つのエッジに接続します.これはきっと優秀に違いない.次に、最終回答の(w[u]&w[v])の値pを列挙することを考慮する.(x&w[u]leq w[u])のため、pを逆さに列挙し、点uを見つけて(w[u]&p=p)にする.次に、(w[v]&p=p)を満たす他の点(v)から、(u)と同じインターフェースブロックにない点を探します.この2つの点の間をエッジに接続します.貢献は(p)です.万一(w[u]&w[v])が(p)より大きいとしたら.これは不可能であることを証明することができる.pは逆さに列挙されているので、(w[u]&w[v]>p)では間違いなく前にエッジがつながっています.二度と繰り返さない.複雑度(O(2^mmalpha(n))

コード#コード#

/*
* @Author: wxyww
* @Date:   2019-01-21 15:46:58
* @Last Modified time: 2019-01-21 15:53:01
*/
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 1000000 +10;
ll read() {
   ll x=0,f=1;char c=getchar();
   while(c'9') {
      if(c=='-') f=-1;
      c=getchar();
   }
   while(c>='0'&&c<='9') {
      x=x*10+c-'0';
      c=getchar();
   }
   return x*f;
}
int p[N],fa[N];
ll ans;
int find(int x) {
   return fa[x] == x ? x :fa[x] = find(fa[x]);
}
void uni(int x,int y) {
   x = find(x),y = find(y);
   if(rand() & 1) fa[x] = y;
   else fa[y] = x;
}
int main() {   
   srand(time(0));
   int n = read(),m = read();
   for(int i = 1;i <= n;++i) {
      int x = read();
      if(p[x]) ans += x;
      p[x] = x;
   }
   int k = (1 << m);
   for(int i = 1;i <= k;++i) fa[i] = i;
   for(int i = (1 << m) - 1;i;--i) {
      for(int j = 0;j < m && !p[i];++j) p[i] = p[i | (1 << j)];
      int u = p[i];
      if(!u) continue;
      for(int j = 0;j < m;++j) {
         int v = p[i | (1 << j)];
         if(!v) continue;
         if(find(v) != find(u)) {
            ans += i;
            uni(u,v);
         }
      }
   }
   cout<