团(Clique)

题目描述

对于一个包含 $n$ 个节点的无向图，每个节点有一个权值 $w_i$。

若无向图存在一个节点子集，当且仅当该子集中任意两个不同的节点都是相邻的，即为一个团。

一个团的权重是指该子集中所包含的节点权值的总和，问该图中第 $k$ 小的团的权重为多少。

需要注意的是，空集合也认为是一个团。

输入格式

• 第一行：两个整数 $n, k$，表示 $n$ 个节点和第 $k$ 小的团
• 第二行：$n$ 个整数，表示 $w_1, w_2, \dots, w_n$
• 接下来输入 $n$ 行，每行包含 $n$ 个字符 $e_{ij}$，若 $e_{ij}=1$ 表示有一条边连接节点 $i$ 和节点 $j$

输出格式

输出一行表示第 $k$ 小的团权重总和。

若团的数量不足 $k$ 个，输出 $-1$。

样例输入 #1

2 3
1 2
01
10

样例输出 #1

2

数据范围

• 对于 $40\%$ 的数据，保证 $1 \leq n \leq 10$；
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$1 \leq k \leq 10^6$，$0 \leq w_i \leq 10^9$，$e_{ij} \in \{0,1\}$，$e_{ii}=0$，$e_{ij}=e_{ji}$。

知识点与难度

本题涉及的知识点从属于 GESP 七级（图论、优先队列枚举、位集合优化），难度等级：⭐⭐⭐⭐。

测试点分布