Kth Minimum Clique_2019牛客暑期多校训练营（第二场）

题目连接：

https://ac.nowcoder.com/acm/contest/882/D

Description

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.

Input

The first line of input contains two space-separated integers N, K.

The second line of input contains N space-separated integers wi representing the weight of each vertex.

Following N lines each contains N characters eij. There's an edge between vertex i and vertex j if and only if eij = "1".

1 <= N <= 100

1 <= K <= 10^6

0 <= wi <= 10^9

Output

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

Sample Input

2 3

1 2

01

10

Sample Output

Hint

题意

给出一个图的邻接矩阵，求该图的所有完全子图(点属于该图且任意两点有边)中权值第K小的价值，图权值为图中所有点的权值之和

题解：

用类似bfs的策略从0个点开始搜索，利用优先队列每次取出价值最小的子图，第K次出队的子图就是第K小的

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <bitset>

using namespace std;

typedef long long ll;

const int mx = 105;

ll v[mx];

int n, k;

int mp[mx][mx];

bitset<mx> sum[mx];

struct Node {

    bitset<mx> state;

    ll value;

    int last;

    bool operator < (Node other) const {

        return value > other.value;

    }

};

ll solve() {

    priority_queue <Node> Q;

    Node st;

    st.state.reset();

    st.value = 0;

    st.last = 0;

    Q.push(st);

    while (!Q.empty()) {

        k--;

        Node now = Q.top();

        Node next = now;

        Q.pop();

        if (k == 0) return now.value;

        for (int i = now.last+1; i <= n; i++) {

            if ((now.state & sum[i]) == now.state) {

                next = now;

                next.state[i] = 1;

                next.value += v[i];

                next.last = i;

                Q.push(next);

            }

        }

    }

    return -1;

}

char str[mx];

int main() {

    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++) scanf("%lld", &v[i]);

    for (int i = 1; i <= n; i++) {

        scanf("%s", str+1);

        for (int j = 1; j <= n; j++) {

            mp[i][j] = str[j]-'0';

            if (mp[i][j]) sum[i][j] = 1;

        }

    }

    printf("%lld\n", solve());

    return 0;

}

巴特西