285484026

「网络流 24 题」孤岛营救问题
「网络流 24 题」孤岛营救问题题解:建立分层图每一层用二进制状态表示拥有的钥匙。跑spfa就好了#include...
扫描右侧二维码阅读全文
25
2018/10

「网络流 24 题」孤岛营救问题

「网络流 24 题」孤岛营救问题
题解:建立分层图每一层用二进制状态表示拥有的钥匙。跑spfa就好了

#include <bits/stdc++.h>

const int fx[] = {1,-1,0,0},fy[] = {0,0,1,-1},INF = 1000000;

using namespace std;

int n,m,p,k,s,ans;
int door[15][15][15][15],dis[15][15][5000],key[15][15],da[20];
bool ther[15][15][15][15];

struct node{
    int x,y,state;
};

inline void init()
{
    scanf("%d %d %d",&n,&m,&p);
    scanf("%d",&k);
    int a,b,c,d,x;
    da[1] = 1;for(int i = 2;i <= p+1;i++) da[i] = da[i-1] << 1;
    for(int i = 1;i <= k;i++){
        scanf("%d %d %d %d %d",&a,&b,&c,&d,&x);
        door[a][b][c][d] = door[c][d][a][b] = da[x];
        ther[a][b][c][d] = ther[c][d][a][b] = true;
    }
    scanf("%d",&s);
    for(int i = 1;i <= s;i++){
        scanf("%d %d %d",&a,&b,&x);
        key[a][b] |= da[x];
    } 
}

inline bool check(node a,node b,int x){
    if(b.x < 1 || n < b.x) return false;
    if(b.y < 1 || m < b.y) return false;
    if(!ther[a.x][a.y][b.x][b.y]) return true;
    if(!(x&door[a.x][a.y][b.x][b.y])) return false;
    return true;
}

queue<node>Q;
inline void spfa(){
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            for(int q = 0;q <= da[p+1] - 1;q++)
                dis[i][j][q] = INF;

    dis[1][1][key[1][1]] = 0;Q.push((node){1,1,key[1][1]});
    
    while(!Q.empty()){
        node u = Q.front();Q.pop();
        for(int i = 0;i <= 3;i++){
            node v = (node){u.x+fx[i],u.y+fy[i],u.state|key[u.x+fx[i]][u.y+fy[i]]};
            if(check(u,v,u.state) && dis[v.x][v.y][v.state] > dis[u.x][u.y][u.state] + 1){
                dis[v.x][v.y][v.state] = dis[u.x][u.y][u.state] + 1;
                Q.push((node){v.x,v.y,v.state});
            }
        }
    } 
}

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    init();
    spfa();ans = INF;
    for(int i = 0;i <= da[p+1] - 1;i++) ans = min(ans,dis[n][m][i]);
    if(ans == INF) printf("-1\n");
    else printf("%d\n",ans);
    return 0;
}
Last modification:October 25th, 2018 at 03:34 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment