Kth Minimum Clique
2024-09-06 12:41:36
Kth Minimum Clique
题目描述
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.
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 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≤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".
输入
2 3
1 2
01
10
输出
2
说明
An empty set is considered as a clique.
题目链接:https://ac.nowcoder.com/acm/contest/882/D
题意:找到权值第K小的完全子图。
思路:考虑一开始我们所选择的子图是个空集,然后逐步向里面加点。这样加点的方式会导致每一次从当前状态,都会产生多个下一状态(比如当前是空集,我们可以把任意一个点加进去,就会有n种状态),那么若是我们可以找到一种方式,使得我们可以按照状态的权值递增的顺序来遍历这些状态,那么遍历到第K个状态时就是答案。于是我们可以用优先队列来实现这种遍历方式,即优先队列每次将当前已拓展的所有状态中,权值最小的那个拿来去拓展其他状态。但是还一个小问题就是我们要保证我们拓展的状态不能重复也不能遗漏,于是只要每次在当前状态的已选中的点中下标最大的点后面拓展,就可以保证不重复不遗漏了。
#include<bits/stdc++.h>
using namespace std;
int w[];
bitset<>Map[];
char M[][]; struct ss
{
bitset<>state;
long long w; bool operator < (const ss & s)const
{
return w>s.w;
}
}; priority_queue<ss>q;
int n,k;
long long spfa(ss now)
{
q.push(now); while(!q.empty())
{
now=q.top();
q.pop();
k--; if(!k)
return now.w; int pos=;
for(int i=;i<n;i++)if(now.state[i])pos=i+; for(int i=pos; i<n; i++)
{
if(now.state[i]==)
{
if((now.state&Map[i])==now.state)//O(1)拓展新状态
{
now.state[i]=;
now.w+=w[i];
q.push(now);
now.state[i]=;
now.w-=w[i];
}
}
}
}
return -;
} int main()
{
scanf("%d %d",&n,&k); for(int i=; i<n; i++)
scanf("%d",&w[i]);
for(int i=; i<n; i++)
scanf("%s",M[i]); for(int i=; i<n; i++)
for(int j=; j<n; j++)
if(M[i][j]=='')Map[i].set(j); ss now;
now.state.reset();
now.w=; printf("%lld\n",spfa(now));
return ;
}
最新文章
- insert、update select from
- 自顶而下设计FPGA
- Mac OS 中 安装配置软件
- C# PPT 查找替换
- DNS分别在什么情况下使用UDP和TCP
- Mysql通信协议
- WinDbg使用介绍
- C#通过编程方式实现Ping
- HTML5 javascript CSS3 jQuery Mobile一些好用的网站
- ARC————自动引用计数
- SQL Server 2008数据库重命名方法
- cf 189B - Counting Rhombi
- 深入理解spring中的各种注解(转)
- 于win7使用虚拟磁盘隐藏文件
- 恢复SQLServer实例连接
- 多目标遗传算法 ------ NSGA-II (部分源码解析)介绍
- android网络编程之HttpUrlConnection的讲解--上传大文件
- bzoj3238--后缀自动机
- CF908G Original Order
- jquery-ui弹框登录前端写法