TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2777
  • 题目
  • P2777【最大流】[CQOI2014]危桥
    限制 : 时间限制 : 1000 MS   空间限制 : 565536 KB
    问题描述

    Alice 和 Bob 居住在一个由 \(N\) 座岛屿组成的国家,岛屿被编号为 $0$ 到 \(N-1\)
    某些岛屿之间有桥相连,桥上的道路是双向的,但一次只能供一人通行。其中一些桥由于年久失修成为危桥,最多只能通行两次。

    Alice 希望在岛屿 \(a_1\)\(a_2\) 之间往返 \(a_n\) 次(从 \(a1\)\(a2\) 再从 \(a2\)\(a1\) 算一次往返)。
    同时,Bob 希望在岛屿 \(b_1\)\(b_2\) 之间往返 \(b_n\) 次。

    这个过程中,所有危桥最多通行两次,其余的桥可以无限次通行。请问 Alice 和 Bob 能完成他们的愿望吗?

    输入格式

    本题有多组测试数据。

    每组数据第一行包含七个空格隔开的整数,分别为$N$、\(a_1\)\(a_2\)\(a_n\)\(b_1\)\(b_2\)\(b_n\)
    接下来是一个 \(N\)\(N\) 列的对称矩阵,由大写字母组成。矩阵的 \(i\)\(j\) 列描述编号 \(i-1\)\(j-1\) 的岛屿间的连接情况,若为 “O” 则表示有危桥相连:为 “N” 表示有普通的桥相连:为 “X” 表示没有桥相连。

    输出格式

    对于每组测试数据输出一行,如果他们都能完成愿望输出 “Yes”,否则输出 “No”(不含引号)。

    样例输入

    4 0 1 1 2 3 1
    XOXX
    OXOX
    XOXO
    XXOX
    4 0 2 1 1 3 2
    XNXO
    NXOX
    XOXO
    OXOX

    样例输出

    Yes
    No

    提示

    提示

    对于所有数据,$4 \leq N\leq 50,\ 0 \leq a_1, a_2, b_1, b_2 \leq N-1,\ 1 \leq a_n, b_n \leq 50$。