题意

给出n个王国和n*n的矩阵，mp[i][j] 代表第 i 个王国欠第 j 个王国 mp[i][j] 块钱。如果当前的王国处于负债状态，那么这个王国就会被消除，和它相连的王国的债务都会被清除。因此会产生连锁反应，使得最后可能只剩下一个王国。输出对于每种情况，最后可能只剩下的王国有哪些。

思路

一开始的想法就是DFS+状压，但是TLE了，队友和我说没记录状态，那样的复杂度差不多是O（n！）的。后面队友写了一个，疯狂WA。

想了好久都没发现的错误：当时做法是全局记录一个原始的图和一个当前的图，每次修改当前的图（修改双向边），然后DFS完又复原回去，这样会错误。

但是这里修改只要修改单向边就可以了，因为如果把行也修改了，复原的时候把行也复原的话，可能本来在这个状态是被删除的，但是又被复原回去了。

有一个比较暴力的做法就是局部开一个图，然后放进去，最后再放回来。这样肯定不会出错，就是比较耗时。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int N = 20 + 11;

int dp[1<<21], mp[N][N], init[N][N], sum[N], n;

vector<int> ans;

int dfs(int st, int rem) {

	if(~dp[st]) return dp[st];

	if(rem == 1) return dp[st] = 1;

	dp[st] = 0;

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

		if((st >> i) & 1) {

            int tmp = 0;

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

                tmp -= mp[i][j];

            if(tmp >= 0) continue;

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

                mp[j][i] = 0;

            dfs(st ^ (1 << i), rem - 1);

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

                mp[j][i] = init[j][i];

		}

	}

}

int main() {

	int t; scanf("%d", &t);

	while(t--) {

		scanf("%d", &n);

		memset(sum, 0, sizeof(sum));

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

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

				scanf("%d", &mp[i][j]), init[i][j] = mp[i][j];

		memset(dp, -1, sizeof(dp));

		dfs((1 << n) - 1, n);

		ans.clear();

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

			if(dp[1<<i] == 1) ans.push_back(i + 1);

		int sz = ans.size();

		if(!sz) puts("0");

		else for(int i = 0; i < sz; i++)

				printf("%d%c", ans[i], i + 1 == sz ? '\n' : ' ');

	} return 0;

}

/*

1

3

0 -3 1

3 0 -2

-1 2 0

*/

巴特西

UVALive 6255：Kingdoms（状压DFS）

题意

思路

最新文章

热门文章