【位掩码判团/二分】牛客2019多校R2TD Kth minimum Clique
传送门
题目是说给出n<=100个点,和每个点的权值。再由邻接矩阵的方式给出点之间的连通性。
问其中第k小的团的点权和是多少。团就是指的任意两点间都有直接路径联通的联通分量。
n k
V1 V2 .. Vn
string1
string2
..
stringK
输入
2 3
1 2
01
10
输出
2
首先,直接求前 k 大的团不好做,因为团的个数最多可以有2^{100}个。
所以可以转化为判断性问题,也就是说给定一个值 mid ,求再满足权值小于 mid 的情况下是否有 k 个或以上的团。由于k只有1e6,所以可以在搜索的时候进行可行性优化。
这也是常用的思想:将搜索前k大转化为二分判定问题。
想要在一个团的基础上找到下一个可能的点加入以后也成为团,只能暴力搜索。但是若每个点都判断一下和其他点是否联通复杂度会多n倍。
观察到每一行代表的是该点和其他点的连通性。例如第一行的01代表的就是1这个点和2是联通的。
那么需要想到的是,把任意m行的二进制数进行与运算,则得到的是和这m个数都联通的点,这样只要从这m个点里取就一定能形成一个团。
还需要对点权进行排序,加快搜索速度。排序后直接建立图:排名为 i 的点和排名为 j 的点的联通状态。搜索的时候每次取最低位就能保证相对团的大小是相对递增的。
100位的位运算可以用bitset
,也可以用__int128
#include<bits/stdc++.h>
using namespace std;
const int maxn = 101;
typedef long long ll;
typedef __int128 lll;
typedef pair<int,int> pii;
const lll ONE = 1;
char s[maxn][maxn];
pii a[maxn];
lll G[maxn];
ll lmt, k, cnt, n;
int lowbit(lll x)
{
if(x & ((ONE << 50) - 1)) return __builtin_ctzll((ll)(x & ((ONE << 50) - 1)));
else return __builtin_ctzll((ll)(x >> 50)) + 50;
}
void dfs(lll now, lll can, ll sum)
{
if(sum > lmt) return;
cnt++;
if(cnt >= k) return;
while(can)
{
int p = lowbit(can);
can ^= (ONE << p);
dfs(now | (ONE << p), can & G[p], sum + a[p].first);
if(cnt >= k) return;
}
}
bool go(ll x)
{
lmt = x;
cnt = 0;
dfs(0, (ONE << n) - 1, 0);
return cnt >= k;
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i++) scanf("%d", &a[i].first), a[i].second = i, G[i] = 0;
for(int i = 0; i < n; i++) scanf("%s", s[i]);
sort(a, a + n);
reverse(a, a + n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) if(s[a[i].second][a[j].second] == '1') G[i] |= ONE << j;
ll l = 0, r = 1e11;
while(l < r)
{
ll mid = (l + r) >> 1;
if(go(mid)) r = mid;
else l = mid + 1;
}
if(go(l)) cout << l;
else cout << -1;
}
关于__int128
__int128
是GCC的扩展类型,在gcc 4.1.2之后被支持。__int128_t
是旧版对其的实现。__int128
不支持标准输入输出。但是可以进行一切数值类型的运算,包括和int
long long
等类型的互相转化- 声明的时候不会被初始化为0,需要手动赋值为0
发表评论