I.建通道
题意
有n个星球 每个有权值vi
两星球vi和vj建边 花费 lowbit(vi xor vj) 如 lowbit(5)=1 lowbit(8)=8
如果要让n个星球两两相通问最少花费
题解
首先将权值去重（权值相等的点连接代价为 0 ），设去重后有 m 个点，接下来找到最小的二进制位 k ，满足存在 vi 的这个二进制位是 0 且存在 vj 的这个二进制位是 1 ，答案就是 2^k×(m−1) （相当于所有这位是 0 的点与 j 点连边，是 1 的点与 i点连边）。
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
| # include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll data[(int)2e5+5];
ll qpow(ll x,ll y){
ll ans=1;
while(y){
if(y&1)ans*=x;
x*=x;y>>=1;
}
return ans;
}
int main(){
int n;cin>>n;
for(int i=0;i<n;i++)cin>>data[i];
sort(data,data+n);ll k=0;
n=unique(data,data+n)-data;
for(int i=0;i<=30;i++){
bool flag1=0,flag0=0;
for(int j=0;j<n;j++){
if((data[j]>>i)&1)flag1=1;
else flag0=1;
}
if(flag0&&flag1){k=i;break;}
}
cout<<qpow(2,k)*(n-1)<<endl;
}
|