Time Limit: 10 Sec? Memory Limit: 128 MB
Submit: 450? Solved: 187
[Submit][Status][Discuss]

Description

有一些王國陷入了一系列的經(jīng)濟(jì)危機(jī)。在很多年以前，他們私底下互相借了許多錢。現(xiàn)在，隨著他們的負(fù)債被揭發(fā)，王國的崩潰不可避免地發(fā)生了……現(xiàn)在有n個王國，對于每對王國A和B，A欠B的錢被記為d_AB（我們假設(shè)有d_BA=-d_AB成立）。如果一個王國入不敷出（即需要支付超過所能獲得的錢），它就可能破產(chǎn)。每當(dāng)一個王國破產(chǎn)，與它相關(guān)的所有債務(wù)關(guān)系都會被去除，無論是正是負(fù)。而王國們的破產(chǎn)不是一瞬間完成的，而是第一個王國破產(chǎn)后，接下來可能破產(chǎn)的王國再繼續(xù)破產(chǎn)，直到剩下的王國經(jīng)濟(jì)都是穩(wěn)定的。不同的結(jié)局將取決于誰先破產(chǎn)，尤其是有的結(jié)局只會留下一個王國。請你計(jì)算，對于每個王國，是否存在一種結(jié)局使得該王國是唯一的幸存者。

Input

第一行一個正整數(shù)T，表示有T組數(shù)據(jù)。

每組數(shù)據(jù)第一行一個正整數(shù)n，表示有n個王國，1 <= n <= 20。

接下來n行，每行n個整數(shù)，第i行第j個整數(shù)表示d_ij，保證有d_ii = 0, d_ij = -d_ji, |d_ij| <= 10^6。

Output

每組數(shù)據(jù)輸出一行，按照升序輸出所有可能的王國編號，空格隔開，如果沒有一個王國能滿足條件，輸出一個0。

Sample Input

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

Sample Output

1 3

HINT

Source

鳴謝Tjz

?

題解：
?????? ①n很小，考慮狀態(tài)壓縮。

?????? ②用01表示是否破產(chǎn)，然后狀態(tài)轉(zhuǎn)移為：狀態(tài)為布爾量轉(zhuǎn)移。
????????? ? f[i^(1<<(j-1))]=f[i] 表示讓j破產(chǎn)。

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

不因一場宿命而忘卻初衷

不因一世坎坷而殘喘茍活。————汪峰《流年啊 你奈我何》

轉(zhuǎn)載于:https://www.cnblogs.com/Damitu/p/7691848.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ 4057 Kingdoms】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。