牛客第二场 D Kth Minimum Clique —— 第k小团

本文主要是介绍牛客第二场 D Kth Minimum Clique —— 第k小团，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    求第 $k$ 小团

解题思路：

    优先队列暴力枚举每个最小团
    关键在于处理重复的情况

    对于每种情况，只对最后一个 $1$ 出现的位置之后加点
    也就是新增点要在当前团的最后一个点之后
    时间复杂度：$O(k\cdot n\cdot logV\cdot bitset<100>)$

核心：第 $k$ 小团模板

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const ll mod = 1e9 + 7;
const int maxn = 1e2 + 10;
int n, k, w[maxn]; 
bitset <maxn> mp[maxn], t;
char s[maxn];struct Node{ll v;bitset <maxn> u;friend bool operator < (Node A, Node B){return A.v > B.v;}
} p;
priority_queue <Node> q;int main() {scanf("%d%d", &n, &k);for(int i=0; i<n; i++) scanf("%d", w+i);for(int i=0; i<n; i++){scanf("%s", s);int len = strlen(s);for(int j=0; j<len; j++)if(s[j]=='1') mp[i][j] = 1; }q.push({0, t});while(q.size()){p = q.top();q.pop();k--;if(k==0){printf("%lld", p.v);return 0;}int pos = 0;for(int i=0; i<n; i++) if(p.u[i]) pos = i + 1;for(int i=pos; i<n; i++){if((mp[i] & p.u) == p.u){p.u[i] = 1;q.push({p.v + w[i], p.u});p.u[i] = 0;}}}puts("-1");
}

这篇关于牛客第二场 D Kth Minimum Clique —— 第k小团的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---