传送门

题目是说给出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

1. __int128 是GCC的扩展类型，在gcc 4.1.2之后被支持。__int128_t 是旧版对其的实现。
2. __int128 不支持标准输入输出。但是可以进行一切数值类型的运算，包括和int long long 等类型的互相转化
3. 声明的时候不会被初始化为0，需要手动赋值为0