网络流24题之十四孤岛营救问题

内容

填坑

地址：cv1911

题目描述

1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为N 行，东西方向被划分为M列，于是整个迷宫被划分为N×M 个单元。每一个单元的位置可用一个有序数对(单元的行号，单元的列号)来表示。南北或东西方向相邻的2 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成P类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即(N，M)单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入(1，1)单元。另外，麦克从一个单元移动到另一个相邻单元的时间为1，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

«编程任务：

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

输入输出格式

输入格式：

第1行有3个整数，分别表示N,M,P的值。第2 行是1个整数K，表示迷宫中门和墙的总数。第I+2 行（1<=I<=K），有5 个整数，依次为Xi1,Yi1,Xi2,Yi2,Gi：

当Gi>=1时，表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间有一扇第Gi类的门，当Gi=0 时，表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间有一堵不可逾越的墙（其中，|Xi1-Xi2|+|Yi1-Yi2|=1，0<=Gi<=P）。

第K+3行是一个整数S，表示迷宫中存放的钥匙总数。

第K+3+J 行(1<=J<=S)，有3个整数，依次为Xi1,Yi1,Qi：表示第J 把钥匙存放在(Xi1,Yi1)

单元里，并且第J 把钥匙是用来开启第Qi类门的。（其中1<=Qi<=P）。

输入数据中同一行各相邻整数之间用一个空格分隔。

输出格式：

将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解，则输出-1。

输入输出样例

输入样例#1：

输出样例#1：

模型

分层图最短路径问题。

实现

用P位二进制表示当前获得的钥匙状态，建立2^P层图。每层图表示在当前钥匙状态下的地图，每获得一把钥匙进入新的一层，BFS求最短路即可。

代码

#include <cstdio>
#include <cstring>
#include <queue>
#define N 200
#define M N*N*4
#define P 3000
using namespace std;
typedef pair<int,int> Pair;   //first for key,second for point
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct node
{
    int from,to,next,open;
}e[M];
int tot,st[M],key[N],map[N][N],id[N][N];
int n,m,x,y,z,a,b,c,p,f;
void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].open=z;
    e[tot].next=st[x];
    st[x]=tot;
}
queue<Pair>que;
int dis[P][N],vis[P][N];
int s,t;
int spfa()
{
    memset(dis,0x3f,sizeof dis);
    dis[1][s]=0;
    vis[1][s]=1;
    que.push(make_pair(1,s));
    while(!que.empty())
    {
        Pair now=que.front();que.pop();
        vis[now.first][now.second]=0;
        dis[now.first|key[now.second]][now.second]=min(dis[now.first|key[now.second]][now.second],dis[now.first][now.second]);
        now.first|=key[now.second];
        for (int i=st[now.second];i;i=e[i].next)
            if (now.first%(e[i].open<<1)>=e[i].open)  //can access
            {
                if (dis[now.first][e[i].to]>dis[now.first][now.second]+1)
                {
                    dis[now.first][e[i].to]=dis[now.first][now.second]+1;
                    if (!vis[now.first][e[i].to])
                        vis[now.first][e[i].to]=1,que.push(make_pair(now.first,e[i].to));
                }
            }
    }
    int ans=0x3f3f3f3f;
    for (int i=1;i<P;i++)
        ans=min(ans,dis[i][t]);
    if (ans==0x3f3f3f3f) ans=-1;
    return ans;
}
main()
{
    int sum=0;s=1;
    scanf("%d%d%d%d",&n,&m,&p,&f);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            id[i][j]=++sum;
    t=sum;
    memset(map,-1,sizeof map);
    for (int i=1;i<=f;i++)
    {
        scanf("%d%d",&a,&b);a=id[a][b];
        scanf("%d%d",&b,&c);b=id[b][c];
        scanf("%d",&c);map[a][b]=map[b][a]=c;
        if (c)
            add(a,b,1<<c),add(b,a,1<<c);
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            int now=id[i][j];
            for (int k=0;k<4;k++)
            {
                int to=id[i+dir[k][0]][j+dir[k][1]];
                if (map[now][to]==-1&&to) add(now,to,1);
            }
        }
    scanf("%d",&f);
    for (int i=1;i<=f;i++)
        scanf("%d%d%d",&a,&b,&c),key[id[a][b]]+=1<<c;
    printf("%d",spfa());
}

网络流24题之十四 孤岛营救问题

题目描述

输入输出格式

输入输出样例

网络流24题之十四孤岛营救问题