[UVA] 11474 - Dying Tree＠Morris' Blog｜PChome Online 個人新聞台

2013-09-15 22:24:26| 人氣2,057| 回應0 | 上一篇 | 下一篇

[UVA] 11474 - Dying Tree

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

Problem D	Dying Tree	Time Limit : 2 seconds
Once upon the time in the forest, there were lots of trees who were all friends to one another. One of the trees T was very sick. She needed a tree doctor to save her life. As you may already know, trees can't move, but what you probably didn't know is that they can talk. Each tree t1 can talk to tree t2 if the minimum distance between any two branches from each is less than or equal to some value k. All trees decided to help their sick friend by trying to reach a doctor tree. They will continue to tell one another that tree T is sick until some tree S finds a tree doctor (who is at distance d or less from any branch of tree S). S will tell the doctor about her friend so he can go help her. A tree is represented by a set of points representing her branches. A doctor is represented by a single point.
Input
Input begins with a number t < 100 representing the number of test cases; t test cases follow. Each test case begins with 4 integers 0 < n < 100, 0 < m ≤ 10, 0 ≤ k, d ≤ 100 where n is the number of trees in the forest, m is the number of doctors in the forest, k & d are as described above. The next m lines represent the positions of doctors in x, y coordinates. The following lines describe the set of trees in the forest. Each set begins with an integer 0 < b < 10 representing the number of branches this tree has. Followed by b points representing the branches positions. The sick tree is always the first tree in the input. All points coordinates are integers with absolute values less than or equal to 1000.

Output
For each test case determine whether or not the trees can help their friend by finding a doctor for her. If yes, then print "Tree can be saved :)", if no then print "Tree can't be saved :(".

Sample Input	Sample Output
2 3 2 2 3 3 8 7 4 4 0 0 1 1 3 2 2 0 3 6 -1 7 1 8 2 3 -1 -1 2 -3 5 -2 3 2 1 2 3 8 7 4 4 0 0 1 1 3 2 2 0 3 6 -1 7 1 8 2 3 -1 -1 2 -3 5 -2	Tree can be saved :) Tree can't be saved :(
Problem Setter: Asmaa Magdi Special Thanks: Muhammad Magdy Alternate Solution: Sohel Hafiz Illustration: The following diagram depicts Sample #1

題目描述：

現在有一棵瀕死的樹，問能不能(間接或直接)連絡到樹醫。
每一棵樹會用很多點表示，樹與樹之間倘若分支點之間距離小於等於 K 可以代為轉達。

而一棵樹的分支點距離樹醫 D 以內時，則可以傳到樹醫。

題目解法：

把圖建出來，走一趟 dfs 或 bfs 即可。

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int x[15], y[15];
int b[105], tx[105][10], ty[105][10];
vector<int> g[120];
int visited[120];
void dfs(int nd) {
   if(visited[nd])
       return;
   visited[nd] = 1;
   int i;
   for(i = 0; i < g[nd].size(); i++)
       dfs(g[nd][i]);
}
int main() {
   int testcase;
   int N, M, K, D;
   int i, j, k;
   int p, q, r;
   scanf("%d", &testcase);
   while(testcase--) {
       scanf("%d %d %d %d", &N, &M, &K, &D);
       for(i = 0; i < N+M; i++)
           g[i].clear(), visited[i] = 0;
       for(i = 0; i < M; i++)
           scanf("%d %d", &x[i], &y[i]);
       for(i = 0; i < N; i++) {
           scanf("%d", &b[i]);
           for(j = 0; j < b[i]; j++)
               scanf("%d %d", &tx[i][j], &ty[i][j]);
       }
       for(i = 0; i < N; i++) {
           for(p = 0; p < b[i]; p++) {
               for(j = i+1; j < N; j++) {
                   for(q = 0; q < b[j]; q++) {
                       int dx = tx[i][p]-tx[j][q];
                       int dy = ty[i][p]-ty[j][q];
                       if(dx*dx+dy*dy <= K*K) {
                           g[M+i].push_back(M+j);
                           g[M+j].push_back(M+i);
                           q = b[j];
                       }
                   }
               }
           }
       }
       for(i = 0; i < M; i++) {
           for(j = 0; j < N; j++) {
               for(p = 0; p < b[j]; p++) {
                   int dx = x[i]-tx[j][p];
                   int dy = y[i]-ty[j][p];
                   if(dx*dx+dy*dy <= D*D) {
                       g[i].push_back(M+j);
                       g[M+j].push_back(i);
                       p = b[j];
                   }
               }
           }
       }
       dfs(M);
       int ret = 0;
       for(i = 0; i < M; i++)
           ret |= visited[i];
       puts(ret ? "Tree can be saved :)" : "Tree can't be saved :(");
   }
   return 0;
}

我要檢舉

#11474#Dying Tree

台長： Morris

您可能對以下文章有興趣

[UVA][單調性、二分] 12064 - Count the Points Inside

[UVA] 11945 - Financial Management

[UVA][負環] 12202 - Haunted Graveyard

[UVA] 556 - Amazing

人氣(2,057) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 10734 - Triangle Partitioning
此分類上一篇:[UVA][STL] 12318 - Digital Roulette

回應(0)