首页 > 搜索 > DFS搜索 > HDU 3107-A Walk in the Park -动态规划-[解题报告]HOJ
2014
03-02

HDU 3107-A Walk in the Park -动态规划-[解题报告]HOJ

A Walk in the Park

问题描述 :

You are responsible for inspecting the trees located in a park, to make sure they remain healthy. The location of each tree is given to you as a point in the twodimensional plane, distinct from that of every other tree. Due to recentlyreplanted grass, you are only allowed to walk through the park along a collection of paths. Each path is described by an infinite-length horizontal or vertical line in the two-dimensional plane. No tree lies on any path.

You are concerned that it may not be possible to view all the trees in the park from the paths. In particular, a tree is visible only if you can view it by standing on some path while facing in a direction perpendicular to that path; there must be no intervening tree that obstructs your view. Given the geometrical configuration of the park, please report the number of visible trees.

输入:

There will be multiple input sets. For each input set, the first line will contain two integers, N and M , ( 0 < N, M<=100000 ), separated by a space. N is the number of trees, and M is the number of paths.

The next N lines each contain two space-separated integers, X and Y , specifying the coordinates of a tree. X and Y may be any 32-bit integers.

The next M lines each describe a path (a vertical or horizontal line). They have the form x = K or y = K , with no spaces. K may be any 32-bit integer. x and y will be lower case.

End of the input is signified by a line with two space-separated 0′s.

输出:

There will be multiple input sets. For each input set, the first line will contain two integers, N and M , ( 0 < N, M<=100000 ), separated by a space. N is the number of trees, and M is the number of paths.

The next N lines each contain two space-separated integers, X and Y , specifying the coordinates of a tree. X and Y may be any 32-bit integers.

The next M lines each describe a path (a vertical or horizontal line). They have the form x = K or y = K , with no spaces. K may be any 32-bit integer. x and y will be lower case.

End of the input is signified by a line with two space-separated 0′s.

样例输入:

6 3
-1 3
4 2
6 2
6 3
6 4
4 3
x=0
y=-1
y=5
1 2
2 3
x=5
y=5
0 0

样例输出:

5
1

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define cc(x,y) memset((x),(y),sizeof((x)))
#define rep(x,y) for(int (x) = 0;(x) < (y) ; (x) ++)
#define foreach for(Edge* p=adj[now];p;p=p->next)
using namespace std;
const int N = 50010;
const int inf = 10000000;
struct Edge
{
    int v;
    Edge* next;
} *adj[N],*pp,pool[2*N];
void init()
{
    cc(adj,0);
    pp = pool;
}
void addedge(int u,int v)
{
    pp->v =v;
    pp->next = adj[u];
    adj[u] = pp++;
}
int small;
int n;
bool flag[N];
int dp[N];
int ans1,ans2;
void dfs(int now)
{
    flag[now] = true;
    int s = 0;
    dp[now] = 1;
    foreach
    {
        if(!flag[p->v])
        {
            dfs(p->v);
            dp[now] += dp[p->v];
            s = max(s,dp[p->v]);
        }
    }
    s = max(s,n - dp[now]);
    if(s < small)
    {
        small = s;
        ans1 = now;
        ans2 = -1;
    }
    else if(s == small)
    {
        if(ans1 == -1)
            ans1 = now;
        else
            ans2 = now;
    }
}

int main()
{
    while(scanf("%d",&n) == 1)
    {
        small = inf;
        init();
        rep(i,n-1)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        ans1=  ans2= -1;
        cc(flag,0);
        cc(dp,0);
        dfs(1);
        if(ans2 == -1)
            printf("%d\n",ans1);
        else
            printf("%d %d\n",min(ans1,ans2),max(ans1,ans2));
    }
    return 0;
}

  

参考:http://www.cnblogs.com/luyi0619/archive/2011/08/01/2123477.html


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示