当前位置: 代码迷 >> 综合 >> Kth Minimum Clique
  详细解决方案

Kth Minimum Clique

热度:69   发布时间:2024-01-26 11:07:00.0

Kth Minimum Clique

题意: 有一个图,每个节点都有自己的权值,找一个子图,所有节点相加的权值是第k小,(权值为0的图为第一小,也就是空图),且子图的条件是,任意两个点都相邻。

题解:当k==1时,答案是0,当k大于1时,我们先把所有节点加入优先队列中,然后优先队列以权值小的优先,当top出来一个值,再从这个节点能衍生的点加入都优先队列里面。

难点就是,如何判断加入是否与该点相邻,这里要用个很厉害的东西叫bitset,可以百度查下,然后就直接二进制操作了。

#include<bits/stdc++.h>
using namespace std;
const int N = 107;
bitset<N> mp[N];
int n,k,value[N];struct node{long long v;int pos;bitset<N> a;node(){}node(long long v,int pos,bitset<N> a){this->v = v;this->pos = pos;this->a = a;}bool operator<(const node &x)const{return v > x.v;}
};void work(){priority_queue<node> q;for (int i = 1; i <= n;i++){q.push(node(1ll*value[i], i, mp[i]));}if(k==1){printf("0\n");return;}while(!q.empty()){node cd = q.top();q.pop();k--;if(k==1){printf("%lld\n", cd.v);return;}for (int i = cd.pos + 1; i <= n;i++){if(cd.a[i]){q.push(node(1ll * (cd.v + 1ll * value[i]), i, mp[i] & cd.a));}}}printf("-1\n");
}int main(){int x;scanf("%d%d", &n,&k);for (int i = 1; i <= n;i++){scanf("%d" ,& value[i]);}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){scanf("%1d", &x);mp[i][j] = x;}}work();
}
  相关解决方案