搜索专题1

今天给大家分享一下搜索的第一讲。

搜索有很多方式，如：二分，宽搜，深搜等。

今天一共有两题。

第一题：关闭农场

题目描述:

农夫约翰和他的奶牛准备去旅行，所以约翰想要把他的农场临时关闭。

农场有N个牛棚（牛棚从1到N编号），有M条路连接这些牛棚(1≤N,M≤3000)。约翰打算挨个关闭牛棚，在关牛棚的时候，他突然想起一个有趣的问题：剩余的这些没有关闭的牛棚是不是连通呢？连通指的是从任何一个牛棚出发，都能到达其他牛棚（注意：已经关闭的牛棚不可以通行）。

输入格式:

第一行包括两个整数N M，接下来M行，每行输入两个整数x y，表示x和y牛棚之间存在一条路，路是双向通行的。接下来n行，表示关牛棚的顺序。

输出格式:

输出N行：第一行表示初始状态下，牛棚是否连通；接下来N-1行，表示关闭对应牛棚后，剩余牛棚是否联通。如果连通，输出YES，不连通，输出NO。（最后一次关闭不需要输出）。

输入样例:

4 3
1 2
2 3
3 4
3
4
1
2

输出样例:

YES
NO
YES
YES

AC参考代码1：

#include<bits/stdc++.h>
#define N 3010
using namespace std;
vector<int>h[N];//创建动态数组
int n,m,f[N],d[N],ans;
void dfs(int x)
{
  d[x]=1;
  ans++;
  for(int i=0;i<h[x].size();i++)
  {
    int y=h[x][i];
    if(f[y]||d[y])
    {
      continue;
    }
    dfs(y);
  }
}
int main()
{
  scanf("%d%d",&n,&m);
  int x,y;
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d",&x,&y);
        h[x].push_back(y);
        h[y].push_back(x);
  }//输入
  memset(f,0,sizeof(f));
  for(int i=1;i<=n;i++)
  {
    int tmp;
    for(int j=1;j<=n;j++)
    {
      if(f[j]==0)
      {
        tmp=j;
        break;
      }
    }
    ans=0;
    memset(d,0,sizeof(d));//清零
    dfs(tmp);
    if(ans==n-i+1)
    {
      printf("YES\n");//输出
    }
    else
    {
      printf("NO\n");//输出
    }
    scanf("%d",&x);//输入
    f[x]=1;
  }
  return 0;
}

AC参考代码2：

#include<bits/stdc++.h>
using namespace std;
int f[3003];
int fd(int x){
    return x==f[x]?x:f[x]=fd(f[x]);//建造函数
}
vector<int>ck;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int>road[n+1];
    for(int u,v,i=0;i<m;i++){
        cin>>u>>v;
        road[u].push_back(v);
        road[v].push_back(u);
    }//输入
    bool p[n+1],open[n+1];
    int close[n+1];
    for(int i=1;i<=n;i++)
        cin>>close[i];
    memset(open,false,sizeof(open));
    memset(p,true,sizeof(p));//清零
    for(int u,i=n;i;i--){
        u=f[close[i]]=close[i];
        open[close[i]]=true;
        ck.push_back(close[i]);
        if(i==n) continue;
        for(int v,j=0;j<road[close[i]].size();j++){
            if(open[road[close[i]][j]]){
                v=fd(road[close[i]][j]);
                if(v!=u)
                    f[v]=u;
            }
        }                           
        u=fd(ck[0]);
        for(int j=1;j<ck.size();j++){
            if(u!=fd(ck[j])){
                p[i]=false;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(p[i]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;//输出
    return 0; //结束
}

第二题：广播系统

题目描述:

约翰的奶牛们想建立一个广播系统，以避免每次发通知都要大声叫。这个系统总共有n个基站（1<=n<=200），每个基站配备一个广播设备，这个设备可以将信息发送给半径在p氛围内的其它基站。当然了，这些基站可以转播收到的信息（不会转播给发给它信息的基站）。

现在设备已经配备好了，由于每个设备的转播能力不同，为了减少工作量，现在需要选一个广播总站。广播总站的要求是他能把信息传给更多的人。

输入格式:

​第一行输入一个整数n

接下来n行，每行输出三个整数x，y，pi，表示第i个基站的坐标是（x，y），转播范围为pi。（所有数字在0到25000范围内）

输出格式:

​输出用广播总站最多能发送信息给几个站（包括总站）。

输入样例:

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

输出样例:

3

AC参考代码：

#include<bits/stdc++.h>
using namespace std;
#define N 210
int ans,n,f[N];
struct node
{
  int x,y,p;
}a[N];//建立结构体 
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&&!f[i])//判断条件：如果下一个顶点可以被到达，而且以前没有被到达过 
    {
      f[i]=1;//标记 
      dfs(i);//递归 
    }
  }
}//搜索 
int main()//主函数
{
  scanf("%d",&n);//输入
  for(int i=1;i<=n;i++)
  {
    scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].p);//输入 
  }
  for(int i=1;i<=n;i++)
  {
    int sum=0;
    memset(f,0,sizeof(f));//别忘记清零 
    f[i]=1;
    dfs(i);
    for(int j=1;j<=n;j++)
    {
      if(f[j])
      {
        sum++;
      }
    }
    ans=max(ans,sum);
  }
  printf("%d\n",ans);//输出
  return 0;//结束了 
}

今天的分享到此结束，我们下次再见。（希望大家有自己的思考，不要一味着抄代码）