hdu 4607 Park Visit (树的直径,推公式)

Posted by 111qqz on Wednesday, July 13, 2016

TOC

hdu4607题目链接
题意:给出一棵树。。。边权都为1. m个查询。。每个查询给一个k,表示只访问k个点。。。问每次的最小路径和是多少。。。
思路:我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何(深度的意思是说,与和该点最近的直径上的点的距离),距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d,那么k<=d+1的时候,答案为k-1,否则答案为d+(k-d-1)*2。。。

因为bfs的时候忘记标记起点WA了一发蠢哭。。。。2A

/* ***********************************************
Author :111qqz
Created Time :2016年07月13日 星期三 14时33分29秒
File Name :code/poj/4607.cpp
 ************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
vector< int >edge[N];
int n,m;
int d[N];
int lst,beg;
bool vis[N];

void bfs( int s)
{
    ms(d,0);
    ms(vis,false);

    queue<int>q;
    q.push(s);
    vis[s] = true;

    while(!q.empty())
    {
    int u = q.front();
    q.pop();
    //	cout<<"u:"<<u<<endl;
    int siz = edge[u].size();
    for ( int i = 0 ; i <siz ; i++)
    {
        int v = edge[u][i];
        if (vis[v]) continue;
        d[v] = d[u] + 1;
        vis[v] = true;
        q.push(v);
    }
    }
}
int main()
{
#ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
#endif
    int T;
    cin>>T;
    while (T--)
    {
    scanf("%d%d",&n,&m);
    for ( int i = 1 ; i <= n ; i++) edge[i].clear();
    for ( int i = 1 ; i <= n-1 ; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    bfs(1);
    int mx = 0;
    for ( int i = 1 ; i <= n ; i++)
    {
        if (d[i]>mx)
        {
        mx = d[i];
        lst = i;
        }
    }
    //	    cout<<endl;
    bfs(lst);
    mx = 0 ;
    for ( int i = 1 ; i <= n ; i++)
    {
        if (d[i]>mx)
        {
        mx = d[i];
        beg = i;
        }
    }
    //	    cout<<"beg:"<<beg<<" lst:"<<lst<<endl;
    //	    cout<<"mx:"<<mx<<endl; 
    while (m--)
    {
        int x;
        int ans;
        scanf("%d",&x);
        if (x<=mx+1)
        {
        ans = x-1;
        }
        else
        {
        ans = mx + (x-mx-1)*2;
        }
        printf("%d\n",ans);
    }

    }

#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付