hdu4848 DFS 暴搜+ 强剪枝

题意：

给你一个图，然后问你从1出发遍历所有的点的距离和是多少，这里的距离和是每一个点到1的距离的总和，不是选择一条遍历所有点的路径的总长度,时间限制是 8000ms。

思路：

一开始理解错了，以为是选择一条路径能遍历所有点的路径的总长度，如果是这样可以有两种方法一个就是暴搜时间复杂度n!(不可以)，另一个是dp，开dp[i][j] i是状态，j是点（也不可以，状态太大了），所以就蛋疼了，后来发现自己读错题了，what's all,哎！这个题目可以直接暴搜，有两个剪纸，一个就是根据时间剪纸，每一步必须保证后面的所有的时间都来得及，另一个就是如果当前值比答案还大，那么就直接return.

#include<stdio.h>

#include<string.h>



int time[33] ,mark[33];

int dis[33][33];

int n ,ans;

int minn(int x ,int y)

{

   return x < y ? x : y;

}

void Floyd(int n)

{

   for(int k = 1 ;k <= n ;k ++)

   for(int i = 1 ;i <= n ;i ++)

   for(int j = 1 ;j <= n ;j ++)

   dis[i][j] = minn(dis[i][j] ,dis[i][k] + dis[k][j]);

}

void DFS(int frm ,int s ,int len ,int ge ,int sum)

{

   if(s == n)

   {

      ans = minn(ans ,sum);

      return ;

   }

   if(sum > ans) return;

   for(int i = 2 ;i <= n ;i ++)

   if(!mark[i] && len + dis[frm][i] > time[i])

   return;

   for(int i = 2 ;i <= n ;i ++)

   {

      if(!mark[i])

      {

         mark[i] = 1;

         DFS(i ,s + 1 ,len + dis[frm][i] ,ge - 1 ,sum + dis[frm][i] * ge);

         mark[i] = 0;

      }

   }

}

int main ()

{

   int i ,j;

   while(~scanf("%d" ,&n))

   {

      for(i = 1 ;i <= n ;i ++)

      for(j = 1 ;j <= n ;j ++)

      scanf("%d" ,&dis[i][j]);

      for(i = 2 ;i <= n ;i ++)

      scanf("%d" ,&time[i]);

      Floyd(n);

      ans = 1000000000;

      memset(mark ,0 ,sizeof(mark));

      DFS(1 ,1 ,0 ,n - 1 ,0);

      ans == 1000000000 ? puts("-1") : printf("%d\n" ,ans);

   }

   return 0;

}

巴特西

hdu4848 DFS 暴搜+ 强剪枝

最新文章

热门文章