2019牛客暑期多校训练营(第二场)D (bitset)

2019/07/21 21:32
阅读数 12

题意:

让你求出一张图的第$k$小团的权值。

分析:

这道题目相当的有意思!

我们发现我们很难直接高效的算出一张图的第$k$小团的权值。因此,我们考虑将这个问题转化一下。我们发现,因为权值都是正数,因此如果在一个已知的团上能够再增加一个新结点形成团,那么新的团的权值必定增加。因此,我们如果从空集不断往上去增加新的结点构造成团,那么在这个过程中,权值一定是不断增加的。因此我们只需要从小到大拓展团,并将当前的团的权值丢进一个优先队列里进行维护,最后不断获取到第$k$小的权值即可。至此,我们需要考虑如何能够高效的在一个团上增加新的结点。

如果一个结点$a_i$加入到团$S$中,还能够形成团,那么意味着$a_i$一定跟团$S$中的每一个结点都有连边。考虑到在邻接矩阵,有无边是通过$01$的状态维护,因此我们在此可以考虑用$\text{bitset}$代替邻接矩阵进行优化。此时点$a_i$跟其他点的连边状态我们可以用一个$\text{bitset}$:$bit_1$来表示,团的状态也可以用一个$\text{bitset}$:$bit_2$来表示,那么,那么判断团中的结点是否跟$a_i$相连,我们只需要用$&$运算即可解决。

如此一来,我们就可以通过$\mathcal{O}(klogk)$的时间复杂度解决这个问题。

#include <bits/stdc++.h>
#define maxn 105
using namespace std;
typedef  long long ll;
struct Node{
    ll w;
    bitset<maxn>bit;
    Node(){}
    Node(ll _w,bitset<maxn> _bit){
        w=_w,bit=_bit;
    }
    bool operator <(const Node b)const{
        return b.w<w;
    }
};
bitset<maxn> edge[maxn];
int n,k,a[maxn];
char str[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        scanf("%s",str+1);
        for(int j=1;j<=n;j++){
            if(str[j]=='1')
                edge[i].set(j);
        }
    }
    priority_queue<Node>que;
    bitset<maxn> b1;
    ll val=0;
    b1.reset();
    que.push(Node(val,b1));
    for(int i=1;i<=k;i++){
        if(que.empty()){
            puts("-1");
            return 0;
        }
        if(i==k){
            printf("%lld\n",que.top().w);
            return 0;
        }
        b1=que.top().bit,val=que.top().w;
        que.pop();
        int z=1;//为了保证不会重复加点,我们每次从一个已经加入的点的后一个结点开始枚举新加入的结点。
        for(int j=1;j<=n;j++){
            if(b1[j]) z=j+1;
        }
        for(int j=z;j<=n;j++){
            if(b1[j]==0&&( (b1&edge[j])==b1)){
                bitset<maxn>b2;
                b2=b1, b2.set(j);
                que.push(Node(val+a[j],b2));
            }
        }
    }
    return 0;
}
展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部