首页 > ACM题库 > HDU-杭电 > HDU 3570-More happiness[解题报告]HOJ
2014
11-27

HDU 3570-More happiness[解题报告]HOJ

More happiness

问题描述 :

As you know, poor XMM has been dreaming to go to Happyvalley for a long time. The good news is that today her mom finally agreed to take her there this weekend!
In order to make her journey in Happyvalley happier, XMM bought a map of Happyvalley to design a good plan. Happyvalley has N scenic spots which are connected by roads. XMM found that there is exactly one path between each two spots.
XMM can start her journey from arbitrary scenic spot. Several minutes are required for her to walk from one end to the other end on each road. Also, she would spend X minutes for each spot she visit. However, many reasons, such as XMM’s mood, weather condition and so on, may alter X. So there are many possible values of X.
Mom told XMM that she would stay in Happyvalley for only P minutes. Given the information of Happyvalley and the total time P minutes, also, with the time X XMM guesses she would spend in each spot, can you tell XMM the maximum number of spots she may visit? Note that each spot should be counted only once.

输入:

The first line of the input is T (no more than 10), which stands for the number of test cases you need to solve.
On the first line of each test case, there are two numbers, N (no more than 200) and P (no more than 2000000). The following N-1 lines state the roads in the form of “a b c” which means it takes XMM c minutes to walk from spot a to spot b or from b to a (1 <= a, b <= N, 1 <= c <= 10000).
Then an integer Q (no more than 10000) in a single line is the number of all possible value X may be. Each of the following Q lines gives a possible X (no more than 10000).

输出:

The first line of the input is T (no more than 10), which stands for the number of test cases you need to solve.
On the first line of each test case, there are two numbers, N (no more than 200) and P (no more than 2000000). The following N-1 lines state the roads in the form of “a b c” which means it takes XMM c minutes to walk from spot a to spot b or from b to a (1 <= a, b <= N, 1 <= c <= 10000).
Then an integer Q (no more than 10000) in a single line is the number of all possible value X may be. Each of the following Q lines gives a possible X (no more than 10000).

样例输入:

3
3 10
1 2 2
2 3 1
3
10
2
4
6 15
1 2 2
1 3 1
2 6 3
5 3 5
3 4 3
4
1
2
3
100
4 2000000
1 2 1
1 3 1
1 4 1
1
1

样例输出:

Case 1:
1
3
2
Case 2:
5
4
3
0
Case 3:
4

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 210;
const int INFINITE = 0x3F3F3F3F ;
int dp[MAXN] , f0[MAXN][MAXN] , f1[MAXN][MAXN] , f2[MAXN][MAXN] , n , m , p ;
vector< pair<int , int> > e[MAXN] ;
int tot[MAXN] ;

void dfs(int u,int fa)
{
 tot[u] = 1 ;
 for (int i = 0 ; i < e[u].size() ; i++)
 {
 int v = e[u][i].first ;
 if (v == fa) continue ;
 dfs(v,u) ;
 tot[u] += tot[v] ;
 }

 f0[u][1] = f1[u][1] = f2[u][1] = 0 ;
 for (int i = 2 ; i <= tot[u] ; i++)
 f0[u][i] = f1[u][i] = f2[u][i] = INFINITE ;
 for (int i = 0 ; i < e[u].size() ; i++)
 {
 int v = e[u][i].first , w = e[u][i].second ;
 if (v == fa) continue ;
 for (int j = tot[u] ; j > 1 ; j--)
 {
 for (int k = 1 ; k < j && k <= tot[v] ; k++)
 {
 f2[u][j] = min(f2[u][j] , f2[u][j-k] + f2[v][k] + 2 * w) ;

 f1[u][j] = min(f1[u][j] , f2[u][j-k] + f1[v][k] + w) ;
 f1[u][j] = min(f1[u][j] , f1[u][j-k] + f2[v][k] + 2 * w) ;

 f0[u][j] = min(f0[u][j] , f1[u][j-k] + f1[v][k] + w) ;
 f0[u][j] = min(f0[u][j] , f2[u][j-k] + f0[v][k] + 2 * w) ;
 f0[u][j] = min(f0[u][j] , f0[u][j-k] + f2[v][k] + 2 * w) ;
 }
 }
 }
 for (int i = 1 ; i <= tot[u] ; i++)
 {
 dp[i] = min(dp[i] , f0[u][i]) ;
 dp[i] = min(dp[i] , f1[u][i]) ;
 dp[i] = min(dp[i] , f2[u][i]) ;
 }
}

int main()
{
 //freopen("input.txt","r",stdin) ;
 int T , cas=0 ;
 scanf("%d",&T);
 while (T--)
 {
 scanf("%d%d",&n,&p);
 for (int i = 1 ; i <= n ; i++)
 e[i].clear() ;
 for (int i = 1 ; i < n ; i++)
 {
 int u , v , w ;
 scanf("%d%d%d",&u,&v,&w);
 e[u].push_back(make_pair(v,w)) ;
 e[v].push_back(make_pair(u,w)) ;
 }
 for (int i = 1 ; i <= n ; i++)
 dp[i] = INFINITE ;
 dfs(1,-1) ;
 scanf("%d",&m);
 printf("Case %d:\n",++cas) ;


 while (m--)
 {
 int X ;
 scanf("%d",&X) ;
 int ans = 0 ;
 for (int i = 1 ; i <= n ; i++)
 {
 if (dp[i] + i*X > p) break ;
 ans = i ;
 }
 printf("%d\n",ans) ;
 }
 }
 return 0 ;
}

  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?