P4662 [BalticOI 2008]黑手党

    • 39通过
    • 125提交
  • 题目提供者 和泉正宗
  • 评测方式 云端评测
  • 标签 后缀数组,SA 最大流 最小割 BalticOI 2008 Special Judge 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 32MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Byteland 国警方收到了一条匿名举报,其中说当地黑帮老大正计划一次从港口到郊区仓库的运输。警方知道运输的时间并且知道运输需要用到国家的高速公路网。

    高速公路网包含双向的高速公路段,每个路段直接连着两个不同的收费站。一个收费站可能与很多其他的收费站相连。汽车只能通过收费站进入或离开高速公路网。据所知,黑帮会距港口边最近的收费站进入高速公路,从距仓库最近的收费站离开(不会在出高速后重新进入)。特警组位于选定的收费站处。当运输车辆进入被监控的收费站时,它就会被警察抓住。

    从这个角度看,最简单的办法就是在每个收费站处都安排特警班。然而,控制一个收费站需要特定的费用,每个收费站费用不同。警方想要让花费最小,所以他们需要制定一个收费站的最小控制集,这个集合满足两个条件:

    • 所有从港口到仓库的交通必须至少经过集合中的一个收费站
    • 监控这些收费站的费用(即监控每一个收费站费用之和)最小

    你可以假设使用高速公路可以从港口到仓库。

    任务

    写一个程序能够:

    • 从标准输入中读取高速公路网,监控代价和运输的起点和终点
    • 找到收费站的最小控制集
    • 输出这个集合到标准输出

    输入输出格式

    输入格式:

    标准输入的第一行包含两个整数 $n$ 和 $m$,表示收费站的总数和公路段的总数。收费站按 $1$ 到 $n$ 标号;

    第二行包含两个整数 $a$ 和 $b$,分别表示距港口和仓库最近的两个收费站编号;

    接下来 $n$ 行表示控制费用,第 $i$ 行包含一个整数,表示第 $i$ 个收费站的控制费用 $c$;

    接下来 $m$ 行表示高速公路网,第 $j$ 行包含两个整数 $x$ 和 $y$,表示在 $x$ 和 $y$ 收费站之间有一条公路段相连。每一条高速公路段只出现一次。

    输出格式:

    唯一的一行输出应包含最小控制集中收费站的编号,以递增顺序输出,用一个空格分隔。

    如果有多于一个最小控制集,你的程序可以输出任意一个。

    输入输出样例

    输入样例#1: 复制
    5 6
    5 3
    2
    4
    8
    3
    10
    1 5
    1 2
    2 4
    4 5
    2 3
    3 4
    输出样例#1: 复制
    1 4

    说明

    样例解释

    0

    这张图片显示了高速公路网中收费站的编号(在左上角)和控制费用。$1$ 号和 $4$ 号收费站组成了最小控制集,总控制费用为 $5$。

    数据范围

    对于 $40\%$ 的测试数据,$n\le 20$;

    对于全部数据,$1\le n\le 200,1\le m \le 2\times 10^4$​​,$1 \le a,b \le n,a≠b$,$1\le c\le 10^7$​​,$1\le x<y\le n$。

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