HDU4848 Wow! Such Conquering! —

HDU4848 Wow! Such Conquering! —— dfs + 剪枝

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4848

题解：一开始读错题目。以为每个点只能访问一遍。其实只要每个点都有被访问就可以了。

首先是用弗洛伊德算法求出每两点之间的最短路。然后再用dfs搜索。注意剪枝，否则会超时。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <vector>
 7 #include <map>
 8 #include <set>
 9 #include <queue>
10 #include <sstream>
11 #include <algorithm>
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define ms(a, b)  memset((a), (b), sizeof(a))
16 #define eps 0.0000001
17 typedef long long LL;
18 const int INF = 2e9;
19 const LL LNF = 9e18;
20 const int maxn = 2000000+10;
21 const int mod = 1e9+7;
22 
23 int dis[35][35],deadline[35];
24 int vis[35];
25 int n,ans;
26 
27 void dfs(int u, int cnt, int time, int sum)
28 {
29     if(cnt==n)
30     {
31         ans = min(ans,sum);
32         return;
33     }
34 
35     //剪枝：
36     if(sum+time*(n-cnt)>=ans) return;
37     for(int i = 2; i<=n; i++)
38         if(!vis[i] && time+dis[u][i]>deadline[i]) return;
39 
40     for(int i = 2; i<=n; i++)
41     {
42         if(!vis[i])
43         {
44             vis[i] = 1;
45             dfs(i,cnt+1,time+dis[u][i], sum+time+dis[u][i]);
46             vis[i] = 0;
47         }
48     }
49 }
50 
51 void solve()
52 {
53     for(int i = 1; i<=n; i++)
54         for(int j = 1; j<=n; j++)
55             scanf("%d",&dis[i][j]);
56 
57     for(int i = 2; i<=n; i++)
58         scanf("%d",&deadline[i]);
59 
60     for(int k = 1; k<=n; k++)//弗洛伊德算法
61         for(int i = 1; i<=n; i++)
62             for(int j = 1; j<=n; j++)
63                 dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
64 
65     ans = INF;
66     ms(vis,0);
67 
68     dfs(1,1,0,0);
69     if(ans!=INF)
70         printf("%d
",ans);
71     else
72         puts("-1");
73 }
74 
75 int main()
76 {
77     while(scanf("%d",&n)!=EOF){
78         solve();
79     }
80     return 0;
81 }

View Code