poj 3311 Hie with the Pie （状压dp）（Tsp问题）

这道题就是Tsp问题，稍微加了些改变

注意以下问题

（1）每个点可以经过多次，这里就可以用弗洛伊德初始化最短距离

（2）在循环中集合可以用S表示更清晰一些

（3）第一维为状态，第二维为在哪个点，不要写混。

（4）在dp过程中0这个点是不用的，只用到1到n这个点

而实际上dp过程中用的是0到n-1，所以就枚举1到n，然后涉及到集合的地方就写i-1

其他地方如dp的第二维，距离这些都不变。

还有一个方法，是我一开始想的方法，就是在输入的时候就把0放到第n个点，其他下标-1

（4）这道题求最小值，一定要先初始化为最大值

方法一（涉及到集合的时候下标-1）

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 15;

int dist[MAXN][MAXN], dp[1 << 11][MAXN], n;

int main()

{

	while(~scanf("%d", &n) && n)

	{

		_for(i, 0, n)

			_for(j, 0, n)

				scanf("%d", &dist[i][j]);

		_for(k, 0, n)

			_for(i, 0, n)

				_for(j, 0, n)

					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

		memset(dp, 0x3f, sizeof(dp));

		_for(i, 1, n) dp[1 << (i - 1)][i] = dist[0][i];

		REP(S, 0, 1 << n)

			_for(i, 1, n) if(S & (1 << (i - 1)))

				_for(j, 1, n) if(S & (1 << (j - 1)))

					dp[S][i] = min(dp[S][i], dp[S^(1<<(i-1))][j] + dist[j][i]);

		int ans = 1e9;

		_for(i, 1, n)

			ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);

		printf("%d\n", ans);

	}

	return 0;

}

方法二（直接在输入的时候改变）

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 15;

int dist[MAXN][MAXN], dp[1 << 11][MAXN], n;

int main()

{

	while(~scanf("%d", &n) && n)

	{

		_for(i, 0, n)

			_for(j, 0, n)

				scanf("%d", &dist[(!i ? n : i - 1)][(!j ? n : j - 1)]);

		_for(k, 0, n)

			_for(i, 0, n)

				_for(j, 0, n)

					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

		memset(dp, 0x3f, sizeof(dp));

		REP(i, 0, n) dp[1 << i][i] = dist[n][i];

		REP(i, 0, 1 << n)

			REP(j, 0, n) if(i & (1 << j))

				REP(k, 0, n) if(i & (1 << k))

					if(j != k)

					dp[i][j] = min(dp[i][j], dp[i^(1<<j)][k] + dist[k][j]);

		int ans = 1e9;

		REP(i, 0, n)

			ans = min(ans, dp[(1 << n) - 1][i] + dist[i][n]);

		printf("%d\n", ans);

	}

	return 0;

}

巴特西

poj 3311 Hie with the Pie （状压dp）（Tsp问题）

最新文章

热门文章

巴特西

poj 3311 Hie with the Pie （状压dp） （Tsp问题）

最新文章

热门文章

poj 3311 Hie with the Pie （状压dp）（Tsp问题）