本文主要是介绍POJ 3311--佛洛依德枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
有 n 个地点，之后告诉你n个地点的之间的距离，问从起点出发，经过所有的点后再回到起点，求最短路。
输入：
3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0 0
输出：
8
分析：
TSP(旅行商)问题，可以先求出任意两点之间的最短路g[i][j]，直接三重循环的floyed就可以，之后将n个点全排列，枚举所有的状态，找出全排列后的所
有点构成的回路的最小值即可。小技巧：全排列函数next_permutation(v.begin(),v.end())。
代码：
做法：floyed+枚举：
<span style="font-size:14px;">#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<string>
#include<cmath>
#include<vector>
using namespace std;int n, g[11][11];
int main()
{while(scanf("%d", &n) && n){for(int i = 0; i <= n; i++){for(int j = 0; j <= n; j++)scanf("%d", &g[i][j]);}for(int k = 0; k <= n; k++) //floyed任意两点最短路{for(int i = 0; i <= n; i++){for(int j = 0; j <= n; j++)g[i][j] = min(g[i][j], g[i][k] + g[k][j]);}}//之后枚举 n 个节点，所有节点的最小值即可。即：对n个节点全排列vector<int> jeo;for(int i = 1; i <= n; i++) jeo.push_back(i);int ans = -1;do{int tmp = g[0][jeo[0]];for(int i = 1; i < n; i++) tmp += g[jeo[i - 1]][jeo[i]];tmp += g[jeo[n - 1]][0]; //回到起点if (ans == -1 || tmp < ans) ans = tmp; //最小值}while(next_permutation(jeo.begin(), jeo.end()));printf("%d\n", ans);}return 0;
}</span>做法2：
floyed+dp状态压缩：
dp[i][j]是表示i状态下最短路是j,其中i是用十一位二进制表示10个城市，如果去过则标记为1，没有则标记为0.
dp转移方程：dp(s,i)=min(dp(s,i),dp(s^(1<<i-1),k)+dp(k,j)),其中s^(1<<i-1)表示未到达城市i的所有的状态，（1<=k<=n),对于全是1 的
状态，s=(1<<n)-1表示经过所有城市的状态，最终还需要回到起点，所以最后的最小值就是:min(dp(s,i)+dist[i][j])
代码：
#include<iostream>
#define INF 100000000
using namespace std;
int dis[12][12];
int dp[1<<11][12];
int n,ans,_min;
int main()
{ //freopen("in.txt","r",stdin); while(scanf("%d",&n) && n) { for(int i = 0;i <= n;++i) for(int j = 0;j <= n;++j) scanf("%d",&dis[i][j]); for(int k = 0;k <= n;++k) for(int i = 0;i <= n;++i) for(int j = 0;j <= n;++j) if(dis[i][k] + dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k] + dis[k][j]; for(int S = 0;S <= (1<<n)-1;++S)//枚举所有状态，用位运算表示 for(int i = 1;i <= n;++i) { if(S & (1<<(i-1)))//状态S中已经过城市i { if(S == (1<<(i-1))) dp[S][i] = dis[0][i];//状态S只经过城市I，最优解自然是从0出发到i的dis,这也是DP的边界 else//如果S有经过多个城市 { dp[S][i] = INF; for(int j = 1;j <= n;++j) { if(S & (1<<(j-1)) && j != i)//枚举不是城市I的其他城市 dp[S][i] = min(dp[S^(1<<(i-1))][j] + dis[j][i],dp[S][i]); //在没经过城市I的状态中，寻找合适的中间点J使得距离更短，和FLOYD一样 } } } } ans = dp[(1<<n)-1][1] + dis[1][0]; for(int i = 2;i <= n;++i) if(dp[(1<<n)-1][i] + dis[i][0] < ans) ans = dp[(1<<n)-1][i] + dis[i][0]; printf("%d/n",ans); } return 0;
}
这篇关于POJ 3311--佛洛依德枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
