24h購物| | PChome| 登入
2013-08-11 07:03:57| 人氣2,286| 回應0 | 上一篇 | 下一篇

[UVA] 10938 - Flea circus

推薦 0 收藏 0 轉貼0 訂閱站台

Problem E: Flea circus

Sometimes, if you are searching for ladybugs, all you find are tree fleas. An old tree near the anthill serves as a home of two fleas who sometimes steal honeydew from aphids living on the tree. On the old tree, branches connect the forks (spaces where two or more branches meet) and leaves where the fleas can rest. Fleas are so small that the ants cannot see them and thus fleas are safe. Because of their size, the fleas satiate their appetite pretty quickly and then have a lot of energy to jump. They decide to jump toward each other complying with the following rules:

  • There is exactly one way for the fleas to go from one leaf or fork in the tree to another leaf or fork without ever turning back. Each of the fleas starts jumping along such a route to the current location of the other flea.
  • The fleas can only jump from one fork or leaf of the tree to another fork or leaf if they are connected by a branch.
  • If the two fleas land at the same time in the same place then they decide to sit and chat for quite a while.
  • If the two fleas land at the same time in two neighboring places on the tree (forks or leaves) then they keep jumping forever.
The input file contains multiple test cases. Each test case starts with an integer n, the number of leaves and forks in the tree, 1≤n≤5000. We assume that leaves and forks are numbered from 1 to n. Each of the following n-1 lines describe tree branches; each branch is described by two integers a and b, meaning that the branch connects the fork or leaf labeled a and the fork or leaf labeled b. In the (n+1)-st line there is one integer l, 1≤l≤500, saying how many starting positions of the fleas you are to consider for the tree. Each of the following l lines contains two positive integers (not greater than n). These numbers define the tree places in which the fleas start their jumping. Input is terminated by the case with n equal to 0.

Your program should output l lines for each test case. The i-th line for a case should look like

The fleas meet at p.

where p identifies the place where the fleas meet, or

The fleas jump forever between p and r.

where p and r are two neighboring places on the tree with p ≤ r

Sample input

8
1 2
1 3
2 4
2 5
3 6 
3 7
5 8
5
5 1 
7 4
1 8
4 7
7 8
0

Output for sample input

The fleas meet at 2.
The fleas meet at 1.
The fleas jump forever between 2 and 5.
The fleas meet at 1.
The fleas jump forever between 1 and 2.

Piotr Rudnicki


題目描述:


有兩隻跳蚤在樹狀圖形跳,如果他們要碰面的話,會在哪裡碰面?
會有多組兩隻跳蚤的位置,問碰面結果。
如果長度是奇數,則會在中間兩個節點互相跳來跳去,永不會碰面。

題目解法:

由於樹狀圖的兩點路徑只有一條且最短,對其中一點進行 dfs 探索,並且把路徑記錄下來,

搜索到時,則輸出路徑中間的一點或兩點。

#include <stdio.h>
#include <vector>
using namespace std;
vector<int> g[5005];
int st, ed, used[5005] = {}, found, path[5005];
void dfs(int len, int nd) {
    if(used[nd] || found)    return;
    path[len] = nd;
    if(nd == ed) {
        if(len%2 == 0) {
            printf("The fleas meet at %d.\n", path[len/2]);
        } else {
            if(path[len/2] < path[len/2+1])
                printf("The fleas jump forever between %d and %d.\n", path[len/2], path[len/2+1]);
            else
                printf("The fleas jump forever between %d and %d.\n", path[len/2+1], path[len/2]);
        }
        found = 1;
        return;
    }
    used[nd] = 1;
    int i;
    for(i = 0; i < g[nd].size(); i++)
        dfs(len+1, g[nd][i]);
    used[nd] = 0;
}
int main() {
    int n, q, x, y, i;
    while(scanf("%d", &n) == 1 && n) {
        for(i = 1; i <= n; i++)
            g[i].clear();
        for(i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        scanf("%d", &q);
        while(q--) {
            scanf("%d %d", &st, &ed);
            if(st == ed) {
                printf("The fleas meet at %d.\n", st);
                continue;
            }
            found = 0;
            dfs(0, st);
        }
    }
    return 0;
}

台長: Morris
人氣(2,286) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][樹形dp] 11695 - Flight Planning
此分類上一篇:[UVA] 11615 - Family Tree

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文