[UVA] 11474 - Dying Tree
Problem D |
Dying Tree |
Time
Limit : 2 seconds |
||||
|
|
||||||
| 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 |
Tree can be saved :) Tree can't be saved :( |
|||||
Problem Setter: Asmaa Magdi 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;
}