poj 3311Hie with the Pie

时间:2022-10-12 19:18:09

题意:一个送披萨的,每次送外卖不超过10个地方,给你这些地方之间的时间,求送完外卖回到店里的总时间最小。

解法一:

  这个n不大,即使是NP问题也才1E6多一些所以可以dfs();具体的回溯方法结合dance link 就可以;

  

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
int Map[][];
int Stack[],pos;
int left[];
int right[];
int n,ans,tmp,num;//比较怕爆栈 放到内存理好
void inint()
{
ans=0x7fffffff;
pos=;
for(int i=;i<=n;i++)
left[i]=i-,right[i]=i+;
for(int k=;k<=n;k++)for(int i=;i<=n;i++)for(int j=;j<=n;j++)
Map[i][j]=min(Map[i][j],Map[i][k]+Map[k][j]);
}
void make()
{
tmp=Map[][Stack[]];
for(int i=;i<pos;i++)
tmp+=Map[Stack[i-]][Stack[i]];
tmp+=Map[Stack[pos-]][];
ans=min(ans,tmp);
}
void dfs()
{
//system("pause");
if(num==n){make();return;} for(int i=right[];i<=n;i=right[i])
{
num++;
right[ left[i] ]=right[i];
left [ right[i]]=left[i];
Stack[pos++]=i;
dfs();
num--;
right[ left[i] ]=i;
left [ right[i]]=i;
pos--;
}
}
int main()
{
while(~scanf("%d",&n))
{
if(n==) return ; for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&Map[i][j]);
inint();
dfs();
printf("%d\n",ans);
}
return ;
}

解法2 :我交完了发现怎么都是 0MS  我的200多点;

  仔细想了想可以用DP 解决NP 问题 dp[i][j] = min( dp[i][j ] , dp[i^(1<<j)][k] + dis[k][j] );(dp[i][j] 中 i  是二进制数  每一位表示这一味走没走过;

 #include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
const int INF=<<;
int dp[<<][];
int n;
int Map[][];
void inint()
{
dp[][]=;
for(int i=;i<(<<);i++)for(int j=;j<;j++)dp[i][j]=INF; for(int k=;k<=n;k++)for(int i=;i<=n;i++)for(int j=;j<=n;j++)
Map[i][j]=min(Map[i][k]+Map[k][j],Map[i][j]);
}
void solve()
{
for(int i=;i<(<<n);i++)
for(int j=;j<n;j++)
{
if(==(i&(<<j))) continue;
if(i==(<<j)) dp[i][j]=Map[][j+];
else
{
for(int k=;k<n;k++)
if(k!=j&&(i&(<<k)))
dp[i][j]=min(dp[i][j],dp[i^(<<j)][k]+Map[k+][j+]);
}
}
int ans=INF;
for(int i=;i<n;i++)
ans=min(ans,dp[(<<n)-][i]+Map[i+][]);
printf("%d\n",ans);
}
int main()
{
while(~scanf("%d",&n))
{
if(n==)return ;
for(int i=;i<=n;i++)for(int j=;j<=n;j++)
scanf("%d",&Map[i][j]);
inint();
solve();
}
return ;
}