题目: Click here 题意: 有N个公司..每个公司对每个公司有欠款(负数)或者借款(正数)...一个公司如果借款大于欠款就可能倒闭..一个公司倒闭后其对于得债务关系就都没了..问若最
题目:
Click here
题意:
有N个公司..每个公司对每个公司有欠款(负数)或者借款(正数)...一个公司如果借款大于欠款就可能倒闭..一个公司倒闭后其对于得债务关系就都没了..问若最后只存在一个公司,可能是哪些...
题解:
公司倒闭是相继倒闭的..又公司数量不超过20...容易想到状态压缩dp...dp[x]代表在x代表的二进制状态下1代表未倒闭..0代表倒闭了..这种状态是否可以存在..
初始是dp[(1<<n)-1]=true,其他都是false..更新时..枚举去掉其存在的哪位置的1..
找答案..就是看dp[2^0]~dp[2^(n-1)]哪些是true..就是答案....
Program:
#include<iostream>#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#define ll long long
#define oo 1<<29
#define MAXN 500005
#define pi acos(-1.0)
#define esp 1e-30
using namespace std;
bool dp[1<<21];
int h[21][21];
int main()
{
int cases,n,totol,i,x,k,sum;
scanf("%d",&cases);
while (cases--)
{
scanf("%d",&n);
for (i=0;i<n;i++)
for (x=0;x<n;x++)
scanf("%d",&h[i][x]);
totol=(1<<n)-1;
for (i=0;i<=totol;i++) dp[i]=false;
dp[totol]=true;
for (x=totol;x>=0;x--)
if (dp[x])
for(i=0;i<n;i++)
if (x&(1<<i))
{
sum=0;
for (k=0;k<n;k++)
if (x & (1<<k)) sum+=h[i][k];
if (sum>0) dp[x-(1<<i)]=true;
}
x=0;
for (i=0;i<n;i++)
if (dp[1<<i])
if (!x) printf("%d",i+1),x=1;
else printf(" %d",i+1);
if (!x) printf("0");
printf("\n");
}
return 0;
}