DP
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=0xFFFFFFF;
int N,M;
int Ans;
int m[20];
int a[20][20];
int num[65540];
int f[65540][20];
void init()
{
scanf("%d",&N);
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
scanf("%d",&a[i][j]);
for(int i=1;i<=N;++i){
m[i]=1<<(i-1);
num[m[i]]=i;
}
M=(1<<N)-1;
for(int i=1;i<=M;++i)
for(int j=1;j<=N;++j)
f[i][j]=INF;
for(int i=1;i<=N;++i)
f[m[i]][num[m[i]]]=0;
}
void solve()
{
for(int i=1;i<=M;++i){
for(int j=1;j<=N;++j)
for(int k=1;k<=N;++k) if(j!=k)
if((i&m[j])>0&&(i&m[k])>0)
if(f[i][j]>f[i-m[j]][k]+a[k][j])
f[i][j]=f[i-m[j]][k]+a[k][j];
}
}
void out()
{
Ans=INF;
for(int i=1;i<=N;++i)
if(f[M][i]<Ans) Ans=f[M][i];
printf("%d\n",Ans);
}
int main()
{
init();
solve();
out();
return 0;
}
记忆化搜索
#include<cstdio>
#include<cstring>
using namespace std;
int N,M;
int Ans,Max;
int a[20][20];
int f[65546][20];
int dfs(int m,int d)
{
if(f[m][d]<Max) return f[m][d];
int mi=m-(1<<(d-1));
for(int i=1;i<=N;++i)
if((mi&(1<<(i-1)))>0){
int fi=dfs(mi,i);
if(f[m][d]>fi+a[i][d])
f[m][d]=fi+a[i][d];
}
return f[m][d];
}
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
scanf("%d",&a[i][j]);
M=(1<<N)-1;
memset(f,0x7F,sizeof(f));
Max=f[0][0];
for(int i=1;i<=N;++i)
f[1<<(i-1)][i]=0;
Ans=Max;
for(int i=1;i<=N;++i)
if(dfs(M,i)<Ans)
Ans=f[M][i];
printf("%d\n",Ans);
return 0;
}
posted on 2009-08-15 09:49
xfstart07 阅读(201)
评论(0) 编辑 收藏 引用