首页 > ACM题库 > HDU-杭电 > HDU 4123-Bob’s Race[解题报告]HOJ
2015
04-16

HDU 4123-Bob’s Race[解题报告]HOJ

Bob’s Race

问题描述 :

Bob wants to hold a race to encourage people to do sports. He has got trouble in choosing the route. There are N houses and N – 1 roads in his village. Each road connects two houses, and all houses are connected together. To make the race more interesting, he requires that every participant must start from a different house and run AS FAR AS POSSIBLE without passing a road more than once. The distance difference between the one who runs the longest distance and the one who runs the shortest distance is called “race difference” by Bob. Bob does not want the “race difference”to be more than Q. The houses are numbered from 1 to N. Bob wants that the No. of all starting house must be consecutive. He is now asking you for help. He wants to know the maximum number of starting houses he can choose, by other words, the maximum number of people who can take part in his race.

输入:

There are several test cases.
The first line of each test case contains two integers N and M. N is the number of houses, M is the number of queries.
The following N-1 lines, each contains three integers, x, y and z, indicating that there is a road of length z connecting house x and house y.
The following M lines are the queries. Each line contains an integer Q, asking that at most how many people can take part in Bob’s race according to the above mentioned rules and under the condition that the“race difference”is no more than Q.

The input ends with N = 0 and M = 0.

(N<=50000 M<=500 1<=x,y<=N 0<=z<=5000 Q<=10000000)

输出:

There are several test cases.
The first line of each test case contains two integers N and M. N is the number of houses, M is the number of queries.
The following N-1 lines, each contains three integers, x, y and z, indicating that there is a road of length z connecting house x and house y.
The following M lines are the queries. Each line contains an integer Q, asking that at most how many people can take part in Bob’s race according to the above mentioned rules and under the condition that the“race difference”is no more than Q.

The input ends with N = 0 and M = 0.

(N<=50000 M<=500 1<=x,y<=N 0<=z<=5000 Q<=10000000)

样例输入:

5 5
1 2 3
2 3 4
4 5 3
3 4 2
1
2
3
4
5
0 0

样例输出:

1
3
3
3
5

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <deque>
#define INF 50005
#define inf 0x0f0f0f0f
#define mp make_pair

using namespace std;
vector <int> vec[INF],dis[INF];
int F[INF],Dis[INF];
int qmax[INF], qmin[INF];
bool vis[INF];
int n;
void _addedge(int i,int j,int d)
{
    vec[i].push_back(j),dis[i].push_back(d);
    vec[j].push_back(i),dis[j].push_back(d);
}
int BFS(int s)
{
    int n,j,t,siz,now=-1,ans=0; queue <int> q;
    memset(vis,true,sizeof(vis));
    for (Dis[s]=0,vis[s]=false,q.push(s);!q.empty();)
    {
        n=q.front(),q.pop();
        if (now<Dis[n]) now=Dis[n],ans=n;
        for (siz=vec[n].size(),j=0;j<siz;j++)
            if (vis[t=vec[n][j]])
                Dis[t]=Dis[n]+dis[n][j],vis[t]=0,q.push(t);
    }
    return ans;
}

int check(int u){
    int maxhead, minhead, maxtail, mintail;
    maxhead = minhead = 1;
    maxtail = mintail = 0;
    int now = 1,
    ans = 1;
    for(int i=1;i<=n;++i){
        while(maxhead<=maxtail && F[qmax[maxtail]]<=F[i]) --maxtail;
        qmax[++maxtail] = i;
        while(minhead<=mintail && F[qmin[mintail]]>=F[i]) --mintail;
        qmin[++mintail] = i;
        while(maxhead<=maxtail && minhead<=mintail && F[qmax[maxhead]]-F[qmin[minhead]] > u){
            now = min(qmax[maxhead],qmin[minhead])+1;
            while(maxhead<=maxtail && qmax[maxhead] < now) ++maxhead;
            while(minhead<=mintail && qmin[minhead]< now)  ++minhead;
        }
        if(F[qmax[maxhead]]-F[qmin[minhead]] <= u)
            ans =max(ans, i-now+1);
    }
    return ans;
}

int main()
{
    //freopen("1.txt","r",stdin);
    int i,j,m,x,y,z;
    while (scanf("%d%d",&n,&m),n)
    {
        memset(F,0,sizeof(F));
        for (i=1;i<=n;i++) vec[i].clear(),dis[i].clear();
        for (i=1;i<n;i++)
            scanf("%d%d%d",&x,&y,&z),
            _addedge(x,y,z);
        int s1=BFS(1),s2=BFS(s1);
        for (i=1;i<=n;i++)
            F[i]=max(Dis[i],F[i]);
        BFS(s2);
        for (i=1;i<=n;i++)
            F[i]=max(Dis[i],F[i]);
        while(m--){
            int k;
            scanf("%d",&k);
           /* int l = 1, r = n, mid;
            while(l<=r){
                mid = (l+r)>>1;
                if(check(mid, k)) l = mid+1;else
                r = mid-1;
            }*/
            printf("%d\n",check(k));
        }
    }
    return 0;
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮