2019牛客暑期多校训练营（第二场）D bitset

题意

给一个n个结点的带点权的图，找到第k小的团的权值

分析

用bitset表示团的状态，一个结点必须和团里的每个结点都连边才能加进去，所以可以直接用\(\&\)运算来判断一个结点是否能加进去后还形成团，用优先队列来维护前k小的团的权值。

Code

#include<bits/stdc++.h>

#define fi first

#define se second

#define pb push_back

#define ll long long

using namespace std;

const int inf=1e9;

const int mod=1e9+7;

const int maxn=1e5+10;

int n,k,w[110];

typedef bitset<110> bit;

bit e[110];

struct ppo{

	bit x;

	ll val;

	bool operator <(const ppo &r)const{

		return val>r.val;

	}

};

bool cmp(int x,int y){

	return w[x]<w[y];

}

int main(){

	//ios::sync_with_stdio(false);

	//freopen("in","r",stdin);

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

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

		scanf("%d",&w[i]);

	}

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

		string s;

		cin>>s;

		for(int j=0;j<s.size();j++){

			e[i][j+1]=s[j]-'0';

		}

	}

	priority_queue<ppo>q;

	bit xxg;

	xxg.reset();

	q.push(ppo{xxg,0});

	vector<ll>v;

	while(!q.empty()){

		ppo u=q.top();

		v.pb(u.val);

		if(v.size()>k) break;

		q.pop();

		int z=1;

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

			if(u.x[i]) z=i+1;

		}

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

			if(u.x[i]==1) continue;

			bit ret=e[i]&u.x;

			if(ret==u.x){

				ret[i]=1;

				q.push(ppo{ret,u.val+w[i]});

			}

		}

	}

	sort(v.begin(), v.end());

	if(v.size()<k) puts("-1");

	else printf("%lld\n",v[k-1]);

	return 0;

}

巴特西

2019牛客暑期多校训练营（第二场）D bitset

题意

分析

Code

最新文章

热门文章