专栏首页wym2019 CCPC 秦皇岛 Escape 最大流

2019 CCPC 秦皇岛 Escape 最大流

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/101619358

Problem Description

给一个 n×m 大小的迷宫,左上角为 (1,1) ,右下角为 (n,m) 。迷宫中的每个 1×1 的格子要么是障碍,要么为空。 有 a 个机器人要从迷宫上方走到迷宫下方,其中第 i 个机器人的初始位置为 (1,pi) 的正上方,不妨记为 (0,pi) ,初始运动方向为向下,即 (1,0) 。 迷宫有 b 个出口,其中第 i 个出口位于 (n,ei) 的正下方,不妨记为 (n+1,ei) 。 现在你想要让这些机器人走出迷宫,但是这些机器人只会沿着当前的运动方向走,不会转弯,所以你需要在迷宫中的某些空格子上设置转弯装置,每个格子上最多只能有一个转弯装置,转弯装置有 ``NW'',``NE'',``SW'',``SE'' 4 种,其中:

  • "NW'' 装置会把从格子上方走来的机器人的运动方向变成向左,以及把从格子左方走来的机器人的运动方向变成向上,不允许机器人从格子的右方及下方进入。
  • "NE'' 装置会把从格子上方走来的机器人的运动方向变成向右,以及把从格子右方走来的机器人的运动方向变成向上,不允许机器人从格子的左方及下方进入。
  • "SW'' 装置会把从格子下方走来的机器人的运动方向变成向左,以及把从格子左方走来的机器人的运动方向变成向下,不允许机器人从格子的右方及上方进入。
  • "SE'' 装置会把从格子下方走来的机器人的运动方向变成向右,以及把从格子右方走来的机器人的运动方向变成向下,不允许机器人从格子的左方及上方进入。
  • 你想知道,是否存在一种设置转弯装置的方案,使得所有机器人都能在不经过障碍格子以及不非法进入转弯装置的情况下走出迷宫(允许多个机器人经过同一个格子)。能则输出 ``Yes'',不能则输出 ``No''。

Input

输入第一行一个正整数 T ,表示数据组数。 对于每组数据: 第一行四个正整数 n,m,a,b ,表示迷宫的大小,机器人个数,出口个数。 接下来 n 行,每行一个长为 m 的 01 字符串 si ,表示迷宫,其中第 i 个字符串的第 j 个字符表示迷宫中 (i,j) 的状态 —— 0 表示为空,1 表示为障碍。 接下来一行 a 个互不相同的正整数 pi ,表示机器人的初始位置 (0,pi) 。 接下来一行 b 个互不相同的正整数 ei ,表示出口的位置 (n+1,ei) 。 1≤T≤10 1≤n,m≤100,1≤a,b,pi,ei≤m

Output

输出共 T 行,每行一个字符串 ``Yes'' 或者 ``No'',表示对应数据的答案。

Sample Input

2 3 4 2 2 0000 0011 0000 1 4 2 4 3 4 2 2 0000 0011 0000 3 4 2 4

Sample Output

Yes No

Hint

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x7ffffff
#define sz(i,j) n*m+(i-1)*m+j
#define sp(i,j) (i-1)*m+j 
const int M = 1000005;
const int inf = 0x7fffffff;
struct E {
    int nxt,u,v,w;
};
E edg[M];
int d[M],head[M],cnt;
int s,t,n,m;
void init() {
    cnt = 0;
    memset(head,-1,sizeof head);
}
void add(int u,int v,int w) {
    edg[cnt].v = v;
    edg[cnt].u = u;
    edg[cnt].w = w;
    edg[cnt].nxt = head[u];
    head[u] = cnt++;
    edg[cnt].v = u;
    edg[cnt].u = v;
    edg[cnt].w = 0;
    edg[cnt].nxt = head[v];
    head[v] = cnt++;
}
bool bfs(int s,int t) {
    queue<int> q;
    memset(d,0,sizeof d);
    q.push(s);
    d[s] = 1;
    while(!q.empty()) {
        int top = q.front();
        q.pop();
        for(int i = head[top]; i + 1; i = edg[i].nxt) {
            int v = edg[i].v,w = edg[i].w;
            if(!d[v] && w) {
                d[v] = d[top] + 1;
                q.push(v);
            }
        }
    }
    return d[t] > 0;
}
int dfs(int s,int t,int inflow) {
    if(s == t || !inflow) return inflow;
    int flow = 0;
    for(int i = head[s]; i + 1; i = edg[i].nxt) {
        int v = edg[i].v,w = edg[i].w;
        if(w && d[v] == d[s] + 1) {
            int x = dfs(v,t,min(inflow,w));
            edg[i].w -= x;
            edg[i ^ 1].w += x;
            inflow -= x;
            flow += x;
            if(!inflow) break;
        }
    }
    if(!flow) d[s] = -2;
    return flow;
}
long long dinic(int s,int t) {
    long long ans = 0;
    while(bfs(s,t))
        ans += dfs(s,t,inf);
    return ans;
}
bool vis[105][105];
char ch[105];
int main() {
    int a,b,c;
    int _;
    int num1,num2;
    for(scanf("%d",&_); _; _--) {
        scanf("%d %d %d %d",&n,&m,&num1,&num2);
        init();
        s = n*m*2+5;    t = s+1;
        ll ans = 0;
        for(int i=1; i<=n; i++) {
            scanf("%s",ch);
            for(int j=1;j<=m;j++){
                int p1 = sz(i,j);    
                int p2 = sp(i,j);
                if(ch[j-1]=='0'){
                    if(i-1>=1)add(p1,sz(i-1,j),1);
                    if(i+1<=n)add(p1,sz(i+1,j),1);
                    if(j-1>=1)add(p2,sp(i,j-1),1);
                    if(j+1<=m)add(p2,sp(i,j+1),1);
                    add(p1,p2,1);    add(p2,p1,1);
                }
            } 
        }
        int u;
        for(int i=1;i<=num1;i++){
            scanf("%d",&u);
            u = sz(1,u);
            add(s,u,1);
        }
        for(int i=1;i<=num2;i++){
            scanf("%d",&u);
            u = sz(n,u);
            add(u,t,inf);
        }
        if(dinic(s,t)==num1){
            printf("Yes\n");
        }else {
            printf("No\n");
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [LightOJ-1356] Prime Independence 二分图+素数分解

    数据大,需要用优化的二分图,对每个数求出素因数,不独立的两个数之间就差一个素因数,若 a 去掉这个素因数得到b

    用户2965768
  • P1113 杂务 拓扑

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2965768
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768
  • LeetCode 307. 区域和检索 - 数组可修改(树状数组)

    给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。

    Michael阿明
  • 32.C++-11版本推荐使用using定义别名(替代typedef)

    张诺谦
  • 【2020HBU天梯赛训练】7-30 树的遍历

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    韩旭051
  • 2017icpc beijing-I题-Colored Nodes

    题意:给出n个点m条边 然后每个时间点,与这个位置相连的所有点就会变成这个点的颜色 比如时间1的时候就是以这个位置相连的点2 变成1的颜色同理如下,通过2个循环...

    逐梦的青春
  • 在stm32开发可以调用c标准库的排序和查找 qsort bsearch

    在嵌入式开发中,可以使用c标准库自带的库函数,而不用自己去早轮子,qsort 和bsearch就是其中的两个比较好用的

    用户4645519
  • 01:数制转换

    01:数制转换 总时间限制: 1000ms 内存限制: 65536kB描述 求任意两个不同进制非负整数的转换(2进制~16进制),所给整数在long所能表达...

    attack
  • 图论建图

    图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券