第k小团+bitset优化——牛客多校第2场D

快来打我* 2023-10-11 09:12 3阅读 0赞

模拟bfs，以空团为起点，用堆维护当前最小的团，然后进行加点更新

在加入新点时要注意判重，并且用bitset来加速判断和转移构造

#include<bits/stdc++.h>
    #include<bitset>
    #include<queue>
    using namespace std;
    #define ll long long 
    char mp[105][105];
    int n,k;
    ll a[105];
    bitset<105>bit[105];
    struct Node{
        ll w;
        bitset<105>b;//团内点的状态  
        Node(){w=0;b.reset();}
        Node(ll w,bitset<105>b):w(w),b(b){}
    };
    bool operator<(Node a,Node b){
        return a.w>b.w;
    }
    priority_queue<Node> pq;//团按权值升序排列 
    
    int main(){
        cin>>n>>k;
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(mp[i][j]=='1')bit[i][j]=1;
                else bit[i][j]=0;
            }
        pq.push(Node());
        int cnt=0;ll ans=0;
        while(pq.size()){
            Node cur=pq.top();pq.pop();
    //for(int i=1;i<=n;i++)cout<<cur.b[i];
    //puts(""); 
    
            cnt++;
            if(cnt==k){
                ans=cur.w;
                break;
            }
            //要保证所有在pq里出现过的团都是唯一的，即不能重复加入状态相同的团，
            //更新时只加比当前团最大的点编号大的点 
            int start=1;
            for(int i=n;i>=1;i--)if(cur.b[i]){
                start=i+1;break;
            }
                
            for(int i=start;i<=n;i++)if(!cur.b[i]){
        //第i个点没在团里 
    //for(int j=1;j<=n;j++)cout<<bit[i][j];
    //puts("");
                if((cur.b&bit[i])==cur.b){
                    Node tmp=cur;
                    tmp.w+=a[i];
                    tmp.b[i]=1;    
                    pq.push(tmp);
                }
            }
        }
        
        if(cnt==k)cout<<ans<<endl;
        else cout<<-1<<endl;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11289380.html