本文主要是介绍hdu 3001 Travelling TSP变形 三进制状压dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// hdu 3001 TSP问题的变形
// 这次到每个点最多两次，所以可以用三进制的类推
// dp[S][u]表示当前在u点访问状态为S时所得到的最小的开销
// 采用刷表法，即用当前的状态推出它所能转移的状态
// dp[S][u] 可以到达的状态为dp[S+state[v]][v](dist[u][v]!=inf)
// dp[S+state[v]][v] = max(dp[S+state[v]][v],dp[S][u]+dist[u][v]);
// 其中每个点最多访问2次
// 技巧就是先把所有的状态表示出来visit[S][u];
// 表示当前在u点访问状态为S时u的访问状态。
// 其中我们要求的就是最后每个点都访问过的状态S时的dp[S][v]{v<n};
//
// 这道题开始完全想套一个裸的TSP模板过的，结果样例都过不了
// 哎，发现自己一直很水，继续加油吧。。。
// 而且，犯了一个非常严重的错误，导致调了2个小时的bug
// 哎。。。加油，不过最终还是ac啦
//const int maxn = 15;
//int dp[1<<maxn][maxn];
//int mp[maxn][maxn];
//int n,m;
//void init(){
// int a,b,c;
// memset(mp,0,sizeof(mp));
// memset(dp,0x3f,sizeof(dp));
// for (int i=0;i<m;i++){
// scanf("%d%d%d",&a,&b,&c);
// mp[a][b] = mp[b][a] = c;
// }
// for (int i=0;i<(1<<n);i++)
// dp[i][0] = mp[0][i];
//}
//
//void print(){
// for (int i=0;i<(1<<n);i++){
// for (int j=0;j<n;j++)
// printf("%d ",dp[i][j]);
// puts("");
// }
//}
//
//void solve(){
// for (int S=0;S<(1<<n);S++){
// for (int u=1;u<=n;u++)
// for (int v=1;v<=n;v++){
// if ((S>>v)&1){
// dp[S][u] = min(dp[S][u],dp[S^(1<<v)][v]+mp[v][u]);
// }
// }
// }
// print();
// int ans = 0;
// for (int i=0;i<n;i++)
// ans = max(ans,dp[(1<<n)-1][i]);
// printf("%d\n",ans);
//}
//
//int main() {
// freopen("G:\\Code\\1.txt","r",stdin);
// while(scanf("%d%d",&n,&m)!=EOF){
// init();
// solve();
// }
// return 0;
//}#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define ceil(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define gcd __gcd
#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))
#define popCount __builtin_popcountll
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const long double PI = acos(-1.L);template<class T> inline T lcm(const T& a, const T& b) { return a/gcd(a, b)*b; }
template<class T> inline T lowBit(const T& x) { return x&-x; }
template<class T> inline T maximize(T& a, const T& b) { return a=a<b?b:a; }
template<class T> inline T minimize(T& a, const T& b) { return a=a<b?a:b; }const int maxn = 12;
const int maxm = 60000;
int visit[maxm][maxn];
int dp[maxm][maxn];
int state[maxn];
int mp[maxn][maxn];
const int inf = 0x3f3f3f3f;
int n,m;void print(){for (int i=0;i<n;i++){for (int j=0;j<n;j++)printf("%d ",mp[i][j]);puts("");}
}void init(){memset(mp,inf,sizeof(mp));memset(dp,inf,sizeof(dp));for (int i=0;i<n;i++){dp[state[i]][i] = 0;}int a,b,c;for (int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);a--,b--;mp[a][b] = mp[b][a] = min(mp[a][b],c);}//for (int i=0;i<n;i++)// mp[i][i] = 0;
// print();
}
void solve(){int ans = inf;for (int S=0;S<state[n];S++){bool flag = false;for (int u=0;u<n;u++){if (visit[S][u] == 0) flag = true;if (dp[S][u] == inf) continue;for (int v=0;v<n;v++) if (v!=u){if (visit[S][v]>=2) continue;if (mp[u][v] == inf) continue;dp[S+state[v]][v] = min(dp[S+state[v]][v],dp[S][u]+mp[u][v]);}}if (!flag){for (int u=0;u<n;u++)ans = min(ans,dp[S][u]);}}if (ans == inf)ans = -1;printf("%d\n",ans);}void get(){state[0]=1;for (int i=1;i<=10;i++)state[i] = state[i-1] * 3;for (int S=0;S<=state[10];S++){int x = S;for (int i=0;i<=10;i++){visit[S][i] = x%3;x/=3;}}
}int main() {//freopen("G:\\Code\\1.txt","r",stdin);get();while(scanf("%d%d",&n,&m)!=EOF){init();solve();}return 0;
}
这篇关于hdu 3001 Travelling TSP变形 三进制状压dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
