题意

有一些王国陷入了一系列的经济危机。在很多年以前，他们私底下互相借了许多钱。现在，随着他们的负债被揭发，王国的崩溃不可避免地发生了……现在有n个王国，对于每对王国A和B，A欠B的钱被记为d_AB（我们假设有d_BA=-d_AB成立）。如果一个王国入不敷出（即需要支付超过所能获得的钱），它就可能破产。每当一个王国破产，与它相关的所有债务关系都会被去除，无论是正是负。而王国们的破产不是一瞬间完成的，而是第一个王国破产后，接下来可能破产的王国再继续破产，直到剩下的王国经济都是稳定的。不同的结局将取决于谁先破产，尤其是有的结局只会留下一个王国。请你计算，对于每个王国，是否存在一种结局使得该王国是唯一的幸存者。

\(n \leq 20\)

分析

一看到n=20，考虑状压dp。

用0/1背包\(f(s)\)表示能否以集合\(s\)中的王国作为幸存者。

转移就枚举每个点是否会破产，然后把破产后的状态赋为1即可。

时间复杂度\(O(T \cdot 2^n \cdot n^2)\)，上限很松。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<set>

#include<map>

#include<queue>

#include<bitset>

#include<stack>

#include<algorithm>

#include<cstring>

#define rg register

#define il inline

#define co const

template<class T>il T read()

{

	rg T data=0;

	rg int w=1;

	rg char ch=getchar();

	while(!isdigit(ch))

	{

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

	while(isdigit(ch))

	{

		data=data*10+ch-'0';

		ch=getchar();

	}

	return data*w;

}

template<class T>T read(T&x)

{

	return x=read<T>();

}

using namespace std;

typedef long long ll;

co int MAXN=20;

int n,d[MAXN][MAXN];

bitset <1<<MAXN> ok;

void init()

{

	read(n);

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

		ok[i]=0;

	for(int i=0;i<n;++i)

		for(int j=0;j<n;++j)

			read(d[i][j]);

}

int tmp[MAXN],tcnt;

int ban[MAXN],bcnt;

void work()

{

	ok[(1<<n)-1]=1;

	for(int i=(1<<n)-1;i>=0;--i)

		if(ok[i])

		{

			tcnt=bcnt=0;

			for(int j=0;j<n;++j)

				if(i&(1<<j))

					tmp[tcnt++]=j;

			for(int x=0;x<tcnt;++x)

			{

				int sum=0;

				for(int y=0;y<tcnt;++y)

					sum+=d[tmp[x]][tmp[y]];

				if(sum>0)

					ban[bcnt++]=tmp[x];

			}

			for(int j=0;j<bcnt;++j)

				ok[i-(1<<ban[j])]=1;

		}

	tcnt=0;

	for(int i=0;i<n;++i)

		if(ok[1<<i])

			tmp[tcnt++]=i;

	if(tcnt>0)

	{

		for(int i=0;i<tcnt;++i)

			printf("%d ",tmp[i]+1);

		puts("");

	}

	else

		puts("0");

}

int main()

{

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

//	freopen(".out","w",stdout);

	int T=read<int>();

	while(T--)

	{

		init();

		work();

	}

	return 0;

}

巴特西

BZOJ4057 [Cerc2012]Kingdoms

题意

分析

代码

最新文章

热门文章