P3163 [CQOI2014]危桥

    • 201通过
    • 565提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 最大流 网络流 2014 重庆
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Alice和Bob居住在一个由N座岛屿组成的国家,岛屿被编号为0到N-1。某些岛屿之间有桥相连,桥上的道路是双向的,但一次只能供一人通行。其中一些桥由于年久失修成为危桥,最多只能通行两次。Alice希望在岛屿al和a2之间往返an次(从al到a2再从a2到al算一次往返)。同时,Bob希望在岛屿bl和b2之间往返bn次。这个过程中,所有危桥最多通行两次,其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗?

    输入输出格式

    输入格式:

    本题有多组测试数据。每组数据第一行包含7个空格隔开的整数,分别为N、al、a2、an、bl、b2、bn。接下来是一个N行N列的对称矩阵,由大写字母组成。矩阵的i行j列描述编号i一1和j-l的岛屿间的连接情况,若为”O“则表示有危桥相连:为”N“表示有普通的桥相连:为”X“表示没有桥相连。|

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    4 0 1 1 2 3 1
    XOXX
    OXOX
    XOXO
    XXOX
    4 0 2 1 1 3 2
    XNXO
    NXOX
    XOXO
    OXOX
    输出样例#1: 复制
    Yes
    No
    数据范围
     4

    说明

    4<=N<50

    0<=a1, a2, b1, b2<=N-1

    1 <=an. b<=50

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。