[搜索-bitset]Moocast-S

题面题目描述输入输出 搜索思路$bitset$使用完整代码

题面

题目描述

Farmer John 有 N 头奶牛，他们想组建一个紧急的“传递信息”系统，以便相互之间传递重要的信息。 他们决定使用对讲机来作为装备，而不是通过相互间的哞哞叫，每头牛配有一只对讲机。这些对讲机都有自己的有限传输半径，如果有限传输半径是 $P$ 的话，也就是说该对讲机能将信息传送到与之距离不超过 $P$ 的对讲机（请注意，奶牛$A$ 可能把信息传递给奶牛 $B$，但奶牛 $B$ 却可能没办法把信息传递回去，因为奶牛 A 的有限传输半径大于奶牛 $B$ 的有限传输半径）。幸运的是,奶牛可以通过其他奶牛传递信息，所以没必要每头牛都能直接传送到其他牛。 由于对讲机的这种不对等的性质，其中的一些奶牛传播效果可能比其他奶牛更有效，因为它们能传递到更多的接收者（相互之间产生直接联系）。请帮助奶牛确定：如果源于一头牛，最多能将信息传递到多少头牛？

输入

第 1 行输入奶牛的个数 $N$； 第 2 到 $N+1$ 行，第 $i+1$ 行代表第 $i$ 头奶牛的 $X_i$ 和 $Y_i$坐标，以及其对应对讲机的最大传输半径 $P_i$。

输出

输出共一行一个整数，源于一头牛，最多能将信息传递到多少头牛？原始的这头牛也包含在内。

搜索思路

根据坐标和$P_i$，作出一(或多)张有向图由每个端点找到最多传递的点，求出最大的输出

$bitset$使用

因为需要不跑重复点，且要统计到达点的个数用$bitset$就可以快速实现 bitset用法(fromArvid Y)：bitset详解c++ 对比一下用bitset和不用bitset的

bitsetbools.reset()memset(boo,0,sizeof(boo)搜索搜索if(ans<s.count())for(int i=1;i<=N;i++)x+=boo[i];ans=s.conut()ans=max(ans,x);

完整代码

#include<bits/stdc++.h> using namespace std; int N,ans; int f[239][239]; bitset<239>s(0); struct Q{ int x,y,v; }a[239]; void dfs(int u){ if(s[u]==1)return; s.set(u,1); for(int i=1;i<=N;i++){ if(i!=u&&f[u][i]==1){ dfs(i); } } } int main() { freopen("1.in","r",stdin); scanf("%d",&N); for(int i=1; i<=N; i++) { scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v); } for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { if((double)sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))<a[i].v)f[i][j]=1; } } for(int i=1;i<=N;i++){ s.reset(); dfs(i); if(ans<s.count())ans=s.count(); } printf("%d\n",ans); }