洛谷P3416 Moocast S

題目描述

Farmer John's NN cows (1 \leq N \leq 2001≤N≤200) want to organize an emergency"moo-cast" system for broadcasting important messages among themselves.

Instead of mooing at each-other over long distances, the cows decide to equip themselves with walkie-talkies, one for each cow. These walkie-talkies each have a limited transmission radius -- a walkie-talkie of power PP can only transmit to other cows up to a distance of PP away (note that cow A might be able to transmit to cow B even if cow B cannot transmit back, due to cow A's power being larger than that of cow B). Fortunately, cows can relay messages to one-another along a path consisting of several hops, so it is not necessary for every cow to be able to transmit directly to every other cow.

Due to the asymmetrical nature of the walkie-talkie transmission, broadcasts from some cows may be more effective than from other cows in their ability toreach large numbers of recipients (taking relaying into account). Please help the cows determine the maximum number of cows that can be reached by a broadcast originating from a single cow.

約翰農場主的N(1<=N<=200)頭奶牛想建立一個緊急情況下的“哞哞廣播”系統，這樣它們就可以在自己中間廣播重要資訊。

奶牛們想讓每頭牛裝備上一個對講機，而不是在長距離中向另一頭奶牛“哞哞”亂叫。這些對講機每台都有各自的有效傳輸半徑——一個擁有P能量的對講機隻能向距離在P以内的牛發送資訊（注意可能出現A牛對講機的能量比B牛的大，而A牛可以給B牛發送資訊，但B牛不能傳回資訊）。幸運的是，奶牛們可以通過其他奶牛中繼，沿着一條跳躍的路徑傳遞資訊，是以每個奶牛不必要直接向每個其他奶牛傳播。

由于對講機的費堆成性質，來自一些奶牛的廣播可能比其他奶牛的廣播能夠達到更多的接受者（考慮中繼的情況）的能力更有效。請幫助奶牛确定來自單個奶牛的廣播可以達到的奶牛的最大數量。

輸入格式

The first line of input contains NN.

<p>The next NN lines each contain the xx and yy coordinates of a single cow ( integers in the range 0 \ldots 25,0000…25,000) followed by pp, the power of the walkie-talkie held by this cow.

第一行輸入包括N。

下面的N行，每一行都包括了一隻牛的坐标(x,y),（x,y為整數并且在0...25,000的範圍内）和這隻牛所持有對講機的能量P。

輸出格式

Write a single line of output containing the maximum number of cows a broadcast from a single cow can reach. The originating cow is included in this number.

輸出一行，表示從來自單個奶牛的廣播可以達到的奶牛的最大數量。開始的牛也包括在這個數量中。

輸入輸出樣例

輸入 #1複制

4
1 3 5
5 4 3
7 2 1
6 1 1      

輸出 #1複制

3      

上代碼：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 205;
int ans, n;
int vis[maxn];

//結構體
struct node {
	int x, y, p;
}a[maxn];

//傳回兩點距離
double dis(node a, node b) { 
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

//搜尋
void dfs(int cur) { //cur代表目前的位置
	for (int i = 1; i <= n; i++) {
		if (dis(a[cur], a[i]) <= a[cur].p && !vis[i]) { //判斷條件：如果下一個頂點可以被達到，而且以前沒有被達到過
			vis[i] = 1; //标記
			dfs(i); //遞歸
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y >> a[i].p; //輸入
	}
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		memset(vis, 0, sizeof(vis)); //别忘記清零
		vis[i] = 1;
		dfs(i);
		for (int j = 1; j <= n; j++) 
			if (vis[j]) cnt++;
		ans = max(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}