2019牛客多校第二场 Kth Minimum Clique

淡淡的烟草味﹌ 2021-10-18 07:28 293阅读 0赞

题目描述

Given a vertex-weighted graph with N vertices, find out the K-th minimum weighted clique.  
  
A subset of vertices of an undirected graph is called clique if and only if every two distinct vertices in the subset are adjacent. The weight of a clique is the summation of the weight of vertices in it.

输入描述:

The first line of input contains two space-separated integers N, K.  
The second line of input contains N space-separated integers wiwi representing the weight of each vertex.  
Following N lines each contains N characters eijeij. There's an edge between vertex i and vertex j if and only if eij="1"eij="1".  
  
1≤N≤100  
1≤K≤1e6  
0≤wi≤1e9  
eij∈"01"  
eii="0"  
eij=eji

输出描述:

Output one line containing an integer representing the answer. If there's less than K cliques, output "-1""-1".

示例1

输入

复制

2 3
    1 2
    01
    10

输出

复制

说明

An empty set is considered as a clique.

## 题意： ##

找到第k小权值的团。

## 分析： ##

首先空集一定是最小团。

在空集的加入一个点，可以得到n个新集合。再逐渐往n个集合中加点，又可以得到新集合。

那么我们可以在加点时，保证集合的权值是逐渐变大的。

每次我们可以从所有的现有集合中权值最小的开始更新，所以用到优先队列。

按照这样逐渐加点就可以得到第k小的团，但是可能会有重复或者遗漏，从当前集合标号最大的点之后加点就不会重复遗漏了。

优先队列中存的就是完全子图，完全子图可以用bitset储存。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

///  author:Kissheart  ///
    #include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<string.h>
    #include<vector>
    #include<stdlib.h>
    #include<math.h>
    #include<queue>
    #include<deque>
    #include<ctype.h>
    #include<map>
    #include<bitset>
    #include<set>
    #include<stack>
    #include<string>
    #define INF 0x3f3f3f3f
    #define FAST_IO ios::sync_with_stdio(false)
    const double PI = acos(-1.0);
    const double eps = 1e-6;
    const int MAX=1e5+10;
    const int mod=1e9+7;
    typedef long long ll;
    using namespace std;
    #define gcd(a,b) __gcd(a,b)
    inline ll lcm(ll a,ll b){
          return a/gcd(a,b)*b;}
    inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){
         if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
    inline ll inv1(ll b){
          return qpow(b,mod-2);}
    inline ll exgcd(ll a,ll b,ll &x,ll &y){
         if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
    inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}
    //freopen( "in.txt" , "r" , stdin );
    //freopen( "data.txt" , "w" , stdout );
    int n,k;
    int a[105];
    bitset<105>bit[105];
    struct node
    {
        bitset<105>now;
        ll val;
        int last;
        bool operator < (const node &a) const
        {
            return val>a.val;
        }
    };
    
    ll get_ans()
    {
        priority_queue<node>q;
        node no;
        no.now.reset();
        no.val=0;
        no.last=0;
        q.push(no);
    
        while(!q.empty())
        {
            no=q.top();
            q.pop();
    
            if(--k == 0)
                return no.val;
    
            for(int i=no.last;i<n;i++)
            {
                if(!no.now[i] && ((no.now & bit[i])==no.now) )
                {
                    no.now.set(i);
                    q.push(node{no.now,no.val+a[i],i+1});
                    no.now.reset(i);
                }
            }
        }
        return -1;
    }
    int main()
    {
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                int x;
                scanf("%1d",&x);
                bit[i].set(j,x);
            }
        }
        printf("%lld\n",get_ans());
        return 0;
    }

转载于:https://www.cnblogs.com/Kissheart/p/11224908.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/391720691b944d758bef533bb7a3e12b.png