第k小团(Bitset+bfs)牛客第二场 -- Kth Minimum Clique
2024-09-05 13:09:31
题意:
给你n个点的权值和连边的信息,问你第k小团的值是多少。
思路:
用bitset存信息,暴力跑一下就行了,因为满足树形结构,所以bfs+优先队列就ok了,其中记录下最后进入的点(以免重复跑)。
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#include <cstdio>//sprintf islower isupper
#include <cstdlib>//malloc exit strcat itoa system("cls")
#include <iostream>//pair
#include <fstream>
#include <bitset>
//#include <map>
//#include<unordered_map>
#include <vector>
#include <stack>
#include <set>
#include <string.h>//strstr substr
#include <string>
#include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
#include <cmath>
#include <deque>
#include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
#include <vector>//emplace_back
//#include <math.h>
//#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
#include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
#define mem(a,b) memset(a,b,sizeof(a))
#define fo(a,b,c) for(a=b;a<=c;++a)//register int i
#define fr(a,b,c) for(a=b;a>=c;--a)
#define pr printf
#define sc scanf
void swapp(int &a,int &b);
double fabss(double a);
int maxx(int a,int b);
int minn(int a,int b);
int Del_bit_1(int n);
int lowbit(int n);
int abss(int a);
//const long long INF=(1LL<<60);
const double E=2.718281828;
const double PI=acos(-1.0);
const int inf=(<<);
const double ESP=1e-;
const int mod=(int)1e9+;
const int N=(int)1e6+; int val[];
struct node
{
int End;
long long V;
bitset<> clique;//团
friend bool operator<(node a,node b)
{
return a.V>b.V;
}
};
bitset<> mp[];
priority_queue<node> q; int main()
{
int n,k,i,j;
sc("%d%d",&n,&k);
for(i=;i<=n;++i)
sc("%d",&val[i]);
for(i=;i<=n;++i)
for(j=;j<=n;++j)
{
int t;
sc("%1d",&t);
mp[i][j]=t;
}
bitset<> temp;
q.push({,,temp});
while(!q.empty())
{
node now=q.top();q.pop();
k--;
if(k==)
{
pr("%lld\n",now.V);
return ;
}
for(i=now.End+;i<=n;++i)
{
if((now.clique&mp[i])==now.clique)
{
node v=now;
v.clique[i]=;
v.End=i;
v.V+=val[i];
q.push(v);
}
}
}
pr("-1\n");
return ;
} /**************************************************************************************/ int maxx(int a,int b)
{
return a>b?a:b;
} void swapp(int &a,int &b)
{
a^=b^=a^=b;
} int lowbit(int n)
{
return n&(-n);
} int Del_bit_1(int n)
{
return n&(n-);
} int abss(int a)
{
return a>?a:-a;
} double fabss(double a)
{
return a>?a:-a;
} int minn(int a,int b)
{
return a<b?a:b;
}
最新文章
- C#复习⑦
- __declspec关键字详细用法
- HttpWebRequest代理访问网站
- 自己拼接json字符串,现在用Gson来实现
- 解决Win10系统本地主机,网络受限占用CPU过高的问题
- 【vue】vue全家桶
- SQL Server - CLUSTERED
- React生命周期简单详细理解
- input文件上传(上传单个文件/多选文件/文件夹、拖拽上传、分片上传)
- [问题解决]基于注解配置dubbo遇到ConnectionLoss for /dubbo/xxx问题解决
- redis(2)---redis基本数据类型及常见命令
- [转]LCT讲解
- RF判断列表、字典、整数、字符串类型是否相同方法
- 二叉堆的实现(数组)——c++
- Eclipse最新版注释模板设置详解
- IOS基于XMPP协议开发--XMPPFramewok框架(二):服务器连接
- EntityFramework 学习资料
- 22.NULL 值
- javascript总结17:javascript 函数简介
- 《挑战程序设计竞赛》2.1 穷竭搜索 POJ2718 POJ3187 POJ3050 AOJ0525