Alien Security(dfs+spfa)

84 阅读 0 评论 56 点赞

我是靠谱客的博主包容星月，最近开发中收集的这篇文章主要介绍Alien Security(dfs+spfa)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

You are in charge of security at a top-secret government research facility. Recently your government has captured a live extra-terrestrial (ET) life form, and is hosting an open day for fellow researchers. Of course, not all the guests can be trusted, so they are assigned different security clearance levels. Only guests with a level 5 rating will be allowed into the lab where the extra-terrestrial is being held; other than that, everyone is free to roam throughout the rest of the facility. Each room in the facility is connected via one-way airlocks, so that you can pass through the door in only one direction.

To protect your precious ET you will put in place enhanced security measures (in the form of armed guards) on the route leading to the room containing the ET, but not in the room itself �C the guards do not have sufficient clearance to enter the room containing the ET.

The guards will check the identity and the security rating of all guests trying to pass through the room in which they are stationed, so you would like to place the guards where they will cause the minimum amount of irritation to the guests who have no intention of visiting the ET. The room where the guards must be placed thus satisfies the following two conditions:

1. In order to get to the room containing the ET, the guests must pass through the room containing the guards;

2. There is no other room with this property that is closer to the room containing the ET �C remember, the guards cannot be placed in the room containing the ET itself.

The diagram below illustrates one possible map of your facility:

Note that placing the guards in room 2 would satisfy the first condition, but room 3 is closer to the ET, so the guards must be placed in room 3.

All guests enter through room 0, the entrance to your facility. Your program accepts a sequence of lines containing integers. The first line consists of two integers: the number of rooms, and the room in which the ET is being held (out of his own free will, of course).

The rest of the input is a sequence of lines consisting of only two integers, specifying where the airlock-doors are located. The first number on these lines specifies the source room, and the second the destination room. Remember: you can pass only from the source room to the destination room.

The output of your program consists only of a single line:

Put guards in room N.

where N is the room you've decided to place the guards.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

SAMPLE INPUT

This input sequence specifies the map shown above.

1

9 4
0 2
2 3
3 4
5 3
5 4
3 6
6 5
6 7
6 8
4 7
0 1
1 7
7 0

SAMPLE OUTPUT

Put guards in room 3.

这道题的题意就是，放置一个警卫，然后让所有要看外星人的游客，必须都经过这点，并且这点距离外星人的房间最近，还不能是外星人的房间。

思路就是反向建图，找到每个点到外星人的距离，这样的目的就是能够通过这个距离来更新点。然后开始枚举每一个点，在用dfs，看看删掉此点后能不能从0到达room房间，如果不能的话，并且距离小的话，我们就去更新这个房间。不用管之前是不是能到达，如果不能到达，之前就是无限大，我们自然不会更新，我们是先距离（肯定是能到），再去枚举点，不能到，看看之前的距离是不是小，我们再去更新。。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
/*
还是说一下，我的思路，一开始还是想模拟，就是深搜看看能不能到，能到的话，基本就好了
自己落下了一个条件，就是他要从入口进来的人想要看外星人的都必须被检查，这就尴尬了，自己就不会了
正确的思路，反向建图，从终点想起点走，这样的话，也是满足题意的，还有就是这个必须检查的问题，我们直接
开始进行枚举，如果这个点的这条路上的起点被去掉，现在不能到达外星人的房间了，这就说明这里可能是那个点，毕竟有可能本来就到不了，但是我们还有距离这个条件。
这种反向的思想还是很厉害的
才发现这个题的输入这么变态，没有终止标志。只能采用string来接收，再去转换。
还有这个距离的计算，就是一个单向边，但是还要折腾正反，之前用邻接表都是双向边，这样的话，也没有什么事，
如果用来做这个题的话，也能做出来，只不过可能会麻烦一点，我先用vector来做
还有就是这道题竟然安了回车之后还不结束，再按一次才可以，主要是，这样才是对的，实在是有点变态
*/
int dis[200];//记录距离
int n,room;
vector <int> an[200],rean[200];
int vis[200];
int book[200];//标记是否能够去掉一点之后还能继续到达这一个点
void
spfa(int s)
{
memset(dis,INF,sizeof(dis));
queue<int> q;
q.push(s);
dis[s]=0;//忘记写这句了，开始的位置必定是0,这句话，就像是一个引子，没有这句话，就没有办法启动下面的句子
vis[s]=1;
while(q.size())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=0;i<rean[now].size();i++)//小于没有等于
{
int v=rean[now][i];
if(dis[v]>dis[now]+1)//这个地方就很像广搜了
{
dis[v]=dis[now]+1;
if(!vis[v])
q.push(v),vis[v]=1;
}
}
}
}
int dfs(int s)
{
if(s==room)
return 1;
for(int i=0;i<an[s].size();i++)
if(book[an[s][i]]==0)
{
book[an[s][i]] = 1;//防止出现环，这样的话，深搜就不会停止了，记住这个地方
if(dfs(an[s][i]))//找到直接返回
return 1;
}
return 0;
}
int main()
{
int t;
int flag=0;
scanf("%d",&t);
getchar();
char str[10];//没有办法判断是不是结束，没有具体的输入结束标志
while(t--)
{
memset(vis,0,sizeof(vis));
if(flag) printf("n");flag=1;//提前打印空行
scanf("%d%d",&n,&room);//房间数量 外星人所在的位置
getchar();//这之后就是字符串了，所以我们需要把他们取出来
for(int i=0;i<=n;i++) //清空邻接表
{
an[i].clear();
rean[i].clear();
}
while(gets(str))
{
if(!strcmp(str,""))//空行直接就是回车，所以什么都没有
break;
int u,v;
sscanf(str,"%d %d",&u,&v);//从已经接受的字符串里面来接受数字
an[u].push_back(v);
rean[v].push_back(u);
}
spfa(room);//从终点开始调节路径
int min=INF,id=0;
for(int i=0;i<n;i++)//直接遍历来找最小的，不要总想着可以直接进行访问
{
if(i==room)
continue;//不能在外星人
memset(book,0,sizeof(book));
book[0]=1;
book[i]=1;//去掉这个房间就是提前进行标记
if(dis[i]<min&&!dfs(0))
{
min=dis[i];
id=i;
}
}
printf("Put guards in room %d.n",id);
}
return 0;
}