Kth Minimum Clique（2019牛客暑期多校训练营（第二场）D，K 大完全子图）

一.题目链接：

Kth Minimum Clique

二.题目大意：

有 n 个点，有着各自的点权.

给出连通的边.

求权值 k 大的完全子图.

三.分析：

由于 n ≤ 1e3，所以直接暴搜即可.

这里和状压 DP 有点像，搜索的是状态以及对应的权值.

考虑状态的转移，比如在什么情况下，i 点可以加入.

因为是求完全子图，所以现状态应真包含于 i 点的连接点，否则就不是完全图.

那么怎样判断是否包含呢，用 bitset 可以轻松实现这一点.

不过，这样会有重复.

这个问题可以通过规定状态枚举顺序来解决.

即只在当前状态最后一个 1 之前（如果存在的话）加点.

bitset学习

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)1e2;
const ll inf = 0x3f3f3f3f3f;

struct node
{
    ll w;
    bitset <M + 5> bs;
};

ll w[M + 5];
bitset <M + 5> Edge[M + 5];

struct cmp
{
    bool operator()(node a, node b)
    {
        return a.w > b.w;
    }
};

ll bfs(int n, int k)
{
    ll ans = -1;
    bitset <M + 5> bs;
    priority_queue <node, vector<node>, cmp> q;
    q.push({0, bs});
    struct node p;
    while(!q.empty())
    {
        p = q.top();
        q.pop();
        k--;
        if(!k)
        {
            ans = p.w;
            break;
        }
        int pos = 0;
        for(int i = 0; i < n; ++i)
        {
            if(p.bs[i])
                pos = i;
        }
        for(int i = pos; i < n; ++i)
        {
            if(!p.bs[i] && ((p.bs & Edge[i]) == p.bs))
            {
                p.bs[i] = 1;
                q.push({p.w + w[i], p.bs});
                p.bs[i] = 0;
            }
        }
    }
    return ans;
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; ++i)
        scanf("%lld", &w[i]);
    int x;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            scanf("%1d", &x);
            Edge[i][j] = x;
        }
    }
    ll ans = bfs(n, k);
    printf("%lld\n", ans);
    return 0;
}