Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

12/11
15:19
状压动规

[bzoj 4057] [Cerc2012]Kingdoms

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个正整数T,表示有T组数据。

每组数据第一行一个正整数n,表示有n个王国,1 <= n <= 20。
接下来n行,每行n个整数,第i行第j个整数表示d_ij,保证有d_ii = 0, d_ij = -d_ji, |d_ij| <= 10^6。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

每组数据输出一行,按照升序输出所有可能的王国编号,空格隔开,如果没有一个王国能满足条件,输出一个0。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

1
3
0 -3 1
3 0 -2
-1 2 0

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

1 3

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

状压dp,f[mask]表示有哪些国家破产了可不可行

 

[bzoj 4057] [Cerc2012]Kingdoms