hdu4848 DFS 暴搜+ 强剪枝
DFS 剪枝
2023-09-11 14:13:59 时间
题意:
给你一个图,然后问你从1出发遍历所有的点的距离和是多少,这里的距离和是每一个点到1的距离的总和,不是选择一条遍历所有点的路径的总长度,时间限制是 8000ms。
思路:
给你一个图,然后问你从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; }
相关文章
- hdu4665 DFS
- Aizu - 2305 Beautiful Currency (二分 + DFS遍历)
- 【BZOJ4238】电压 DFS树
- 【BZOJ3551】[ONTAK2010]Peaks加强版 最小生成树+DFS序+主席树
- 复盘:DFS与BFS的主要区别,在思想上的区别,代码实现上的区别
- zoj 1709 dfs
- HDU 4081 Peach Blossom Spring (最小生成树+dfs)
- HDU 4431 Mahjong (DFS,暴力枚举,剪枝)
- HDU 1175 连连看 AND HDU 1728 逃离迷宫 (DFS+剪枝)
- [算法竞赛进阶指南][dfs]递归实现排列型枚举
- 「CodeForces - 717E」Paint it really, really dark gray (dfs)
- 连通块(dfs)java实现
- 127、【贪心算法】leetcode ——455. 分发饼干:DFS+双指针法(C++版本)
- (Relax DFS专题1.2)POJ 2386 Lake Counting(使用DFS来计算有多少坨东西是连通的)
- [递推+dfs]ZOJ 3436. July Number
- hdu1010 dfs+路径剪枝
- 广度优先算法(BFS)与深度优先算法(DFS)
- 【bzoj4009】[HNOI2015]接水果 DFS序+树上倍增+整体二分+树状数组