ZOJ-1085-Alien Security

红太狼 2021-12-13 03:47 235阅读 0赞

[http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1085][http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemCode_1085]

题目大意：

研究机构的每个房间由单向密封过渡仓连接，所以进去只能一个方向通过。

设置守卫室的位置，使其满足一下条件：

1、  要到达et位置，客人必须通过守卫室的房间

2、  没有其他房间更接近放有et的房间，守卫室不能设在et所在的位置

所有客人必须首先进入0号房间，这是入口

程序输入有多行，第一行有两个整数：房间的数目，et所在的位置

其余各行也有两个整数，指明通向，第一个源房间，第二个目标房间，单向。

程序输出只有一行 Put guards in room N.              N是守卫室的位置

题目包含多组数据，第一行是N，表示N组测试数据，每组数据格式与问题描述一样，组数据间有一个空行

算法分析：

刚开始看这道题的时候对题目理解有误，写了程序提交后错了几次，后来看书，才发现题意没有理解清楚，题目要求要到达et，必须经过守卫室，并且次位置最接近et位置实际是要求，守卫室是必要通道，去掉这个位置，就不可能到达et，并且求最近的这样一个点

这道题要用到广度搜索和深度搜索，广度搜索求得各个点到et的最近距离，次题是方向是单向的，从et的位置看，反向看方向即可。

然后一次搜索每个房间i，从0入口，求不经过i就不能到达et的位置，并比较求得一个最接近et的位置

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<queue>
    using namespace std;
    
    #define MAXN 102
    #define inf 1000000
    
    int n,et;
    int data[MAXN][MAXN];    //存储邻接矩阵
    int dist[MAXN],used[MAXN];    //
    
    int dfs(int id)
    {
        if(id == et)        //如果能够到达et，返回1
            return 1;
        used[id] = 1;
        int i;
        for(i=0;i<n;i++)
        {
            if(!used[i] && data[id][i])    //搜索房间id的相邻边
            {
                if(dfs(i))    return 1;
            }
        }
        return 0;
    }
    
    void bfs()    //广度搜索，求得各个顶点到et的最近距离
    {
        int x,y;
        for(x=0;x<n;x++)
            dist[x] = inf;
        dist[et] = 0;
        queue<int> Q;
        Q.push(et);
        while(!Q.empty())
        {
            y = Q.front();    Q.pop();
            for(x=0;x<n;x++)
            {
                if(data[x][y] && dist[y] + 1 < dist[x])
                {
                    Q.push(x);
                    dist[x] = dist[y] + 1;
                }
            }
        }
    }
    
    int main()
    {
        int T,iCase,i,x,y,d,ans;
        char str[10];
        scanf("%d",&T);
        for(iCase=0;iCase<T;iCase++)
        {
            scanf("%d%d\n",&n,&et);
            memset(data,0,sizeof(data));
            while(gets(str))
            {            
                if(strcmp(str,"") == 0)    break;
                sscanf(str,"%d%d",&x,&y);
                data[x][y] = 1;    //有向
            }
            bfs();
            d = dist[0];
            ans = 0;
            for(i=1;i<n;i++)    //
            {
                if(i == et) continue;
                memset(used,0,sizeof(used));
                used[i] = 1;
                if(!dfs(0) && dist[i] < d)    //如果不经过i点，则不能到达et，满足
                {
                    ans = i;
                    d = dist[i];    //更新最短距离
                }
            }
            if(iCase)    printf("\n");
            printf("Put guards in room %d.\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/pcoda/archive/2012/09/02/2667935.html

[http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemCode_1085]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1085