刷题记录:HDU - 3001Travelling

传送门:VJudge

题目描述:

After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He 
has decided to visit n cities(he insists on seeing all the cities!And he does not mind which city being 
his start station because superman can bring him to any city at first but only once.), and of course 
there are m roads here,following a fee as usual.But Mr Acmer gets bored so easily that he doesn't 
want to visit a city more than twice!And he is so mean that he wants to minimize the total fee!He is 
lazy you see.So he turns to you for help.
输入:
2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10
输出:
100
90
7 

吐槽一下HDUoj,我当时没打$!=EOF$居然过不去,az…

对于这道题,是一道三进制状压dp题

对于每一个城市,我们都有三种状态可选,没有经过$/$经过一次$/$经过两次

对于上述的三种状态,我们可以将其转化三进制串进行存储,记为S

那么我们可以是用$dp[S][u]来记录从u点开始走,完成S状态的最小步数$

那么我们的当前结点显然可以由邻接点进行一个转移,当前结点完成S状态,显然可以由邻接点v完成 { s } − u \{s\}-u {s}−u状态.这里可能有人会有疑问,我们的v可能完不成这个状态啊,因为u结点可能恰好是一个转接点,不用慌,对于这种情况,我们只要将初始数据赋值为inf就行,反正最后是取min的,如果没有这个合法状态返回的是inf,那么就没关系了

所以我们可以得出以下的状态转移方程:

$dp[S][u]=min(dp[S][u],dp[S-u][v]+mp[u][[v])$

其中mp[u][v]为两节点之间的边

到此为止这道题的大部分就已经结束了,接下来主要讲一下细节问题:

对于我们的初始状态,因为可以是从任何地方开始的,并且对于任何一个初始的城市开始,我们都可以预处理出它的初始状态(使用tri数组表示):

int tri[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049};

并且因为值三进制状压的话,我们就不能使用二进制状压中使用移位,&,|,之类的简单方式进行操作了,此时我们需要预处理出每一个状态的每一个位的数字:
使用$init()$函数直接进行预处理即可

void init() {
	for(int i=0;i<pow3max;i++) {
		int t=i;
		for(int j=1;j<=10;j++) {
			dig[i][j]=t%3;
			t/=3;
			if(t==0) break;
		}
	}
}

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
const int pow3max=59049;
int dp[pow3max+10][21];
int tri[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049};
int dig[pow3max][21];
void init() {
	for(int i=0;i<pow3max;i++) {
		int t=i;
		for(int j=1;j<=10;j++) {
			dig[i][j]=t%3;
			t/=3;
			if(t==0) break;
		}
	}
}
int n,m;
int mp[21][21];
int main() {
	init();
	while(scanf("%d%d",&n,&m)!=EOF) {
		memset(dp,0x3f,sizeof(dp));
		memset(mp,0x3f,sizeof(mp));
		int ans=inf;
		int a,b,c;
		for(int i=1;i<=m;i++) {
			a=read();b=read();c=read();
			mp[a][b]=mp[b][a]=min(mp[a][b],c);
		}
		for(int i=1;i<=n;i++) dp[tri[i]][i]=0;
		for(int S=0;S<tri[n+1];S++) {
			int vis_all=1;
			for(int u=1;u<=n;u++) {
				if(dig[S][u]==0) {
					vis_all=0;
					continue;
				}
				for(int v=1;v<=n;v++) {
					if(dig[S][v]==0||v==u) continue;
					dp[S][u]=min(dp[S][u],dp[S-tri[u]][v]+mp[u][v]);
				}
			}
			if(vis_all==1) {
				for(int i=1;i<=n;i++) {
					ans=min(ans,dp[S][i]);
				}
			}
		}
		if(ans==inf) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}