hdu 3001(状態圧縮dp、三進!)
Travelling
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5896 Accepted Submission(s): 1908
Problem Description
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.
Input
There are several test cases,the first line is two intergers n(1<=n<=10) and m,which means he needs to visit n cities and there are m roads he can choose,then m lines follow,each line will include three intergers a,b and c(1<=a,b<=n),means there is a road between a and b and the cost is of course c.Input to the End Of File.
Output
Output the minimum fee that he should pay,or -1 if he can't find such a route.
Sample Input
Sample Output
この問題の状態圧縮はバイナリではなく、三進法に変えました!!
これはなぜですか??
问题の中で明确に1点ごとに最大2回歩くことを言って、つまり2進数に圧縮して直接結果を求めることができなくて、2進数は1つの点が通るかどうかの状態を代表することしかできなくて、具体的に何回歩いたことがあっても记录することができません!!しかし、私たちのテーマは2回歩くことができます.どうしよう!牛たちは方法を考えて、3進法に圧縮しました!
状態を3進数に圧縮した後、明らかに私たちの状態数が増えたが、これらの増加した状態数は何を表しているのだろうか.
栗を挙げると、46を3進数にして1201にすると、1番目のポイントに1回、2番目のポイントに2回、3番目のポイントに2回、4番目のポイントにも1回行ったことがあることを暴力的に示すことができます.
上の例で1つの問題を説明して、私达は3進数でテーマの要求のすべての状態を圧縮して、すべての数位が2になることができるため、この2は意味があります!ある点に2回行ったことがあるかどうかを表します!
次にdp部分は状態圧縮の従来の解法であり,主になぜ3進法の状態圧縮にするのかを理解することにある.
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5896 Accepted Submission(s): 1908
Problem Description
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.
Input
There are several test cases,the first line is two intergers n(1<=n<=10) and m,which means he needs to visit n cities and there are m roads he can choose,then m lines follow,each line will include three intergers a,b and c(1<=a,b<=n),means there is a road between a and b and the cost is of course c.Input to the End Of File.
Output
Output the minimum fee that he should pay,or -1 if he can't find such a route.
Sample Input
2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10
Sample Output
100
90
7
この問題の状態圧縮はバイナリではなく、三進法に変えました!!
これはなぜですか??
问题の中で明确に1点ごとに最大2回歩くことを言って、つまり2進数に圧縮して直接結果を求めることができなくて、2進数は1つの点が通るかどうかの状態を代表することしかできなくて、具体的に何回歩いたことがあっても记录することができません!!しかし、私たちのテーマは2回歩くことができます.どうしよう!牛たちは方法を考えて、3進法に圧縮しました!
状態を3進数に圧縮した後、明らかに私たちの状態数が増えたが、これらの増加した状態数は何を表しているのだろうか.
栗を挙げると、46を3進数にして1201にすると、1番目のポイントに1回、2番目のポイントに2回、3番目のポイントに2回、4番目のポイントにも1回行ったことがあることを暴力的に示すことができます.
上の例で1つの問題を説明して、私达は3進数でテーマの要求のすべての状態を圧縮して、すべての数位が2になることができるため、この2は意味があります!ある点に2回行ったことがあるかどうかを表します!
次にdp部分は状態圧縮の従来の解法であり,主になぜ3進法の状態圧縮にするのかを理解することにある.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
int dp[60000][11];///dp[i][j] i j
int three[11];///three[i] 3 i
int digit[60000][11];///digit[i][j] i j （0,1,2）
int tu[15][15];
int n,m;
const int INF=99999999;
void init()
{
three[0]=1;
for(int i=1; i<11; i++)
three[i]=three[i-1]*3;
for(int i=0; i<three[10]; i++)
{
int tem=i;
for(int j=0; j<10; j++)
{
digit[i][j]=tem%3;
tem/=3;
}
}
}
int main()
{
init();
while(~scanf("%d%d",&n,&m))
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
tu[i][j]=INF;
for(int i=0; i<three[n]; i++)
for(int j=0; j<n; j++)
dp[i][j]=INF;
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
tu[a-1][b-1]=tu[b-1][a-1]=min(c,tu[a-1][b-1]);
}
for(int i=0; i<n; i++)
dp[three[i]][i]=0;///dp ，
int ans=INF;
for(int j=0; j<three[n]; j++)
{
bool flag=1;
for(int i=0; i<n; i++)
{
if(digit[j][i]==0)flag=0;/// 0， ，
if(dp[j][i]!=INF)
for(int k=0; k<n; k++)
if(tu[i][k]!=INF&&digit[j][k]!=2)/// digit[j][k]!=2, j k
dp[j+three[k]][k]=min(dp[j][i]+tu[i][k],dp[j+three[k]][k]);
}
if(flag)
for(int i=0; i<n; i++)/// 3 ， 0， dp dp ， T_T
ans=min(ans,dp[j][i]);
}
if(ans>=INF)
printf("-1
");
else
cout<<ans<<endl;
}
return 0;
}