P3511 [POI2010]MOS-Bridges

    • 1通过
    • 77提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 二分答案 最大流 欧拉回路 POI 2010 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    在一个无向图中找一条最大边权最小的欧拉回路。

    题目描述

    San Bytecisco is a beautifully situated coastal town.

    It consists of small, yet densely populated islands, numbered from to .

    Certain islands are connected with bridges, used for (bidirectional) road traffic.

    Each pair of islands can be connected with at most one bridge.

    The islands are connected in such a way that every island can be reached from every other by using the bridges only.

    Byteasar and Bytie are going for a bike trip in San Bytecisco.

    The will start their ride at the island no. 1.

    They intend to visit every island, while passing along every bridge once and ending the trip where it began, i.e., the island no. 1.

    Being quite seasoned riders, they expect some serious trouble from... the wind!

    After all, it is very windy along the coast, and especially so on the bridges between the islands. Obviously, depending on its speed and direction, the wind makes it hard to cross the bridge in different extent for either direction.

    For simplicity we will assume for every bridge and direction of crossing, the opposing wind speed is constant.

    Help Byteasar and Bytie to find a route as they desire that will in addition be the least tiresome. Byteasar and Bytie agreed on the maximum opposing wind speed as a measure of a route's tiresomeness.

    输入输出格式

    输入格式:

    In the first line of the standard input there are two integers separated by a single space: $n$ and $m$ ($2 \le n \le 1000$, $1 \le m \le 2000), denoting the number of islands and the number of bridges in San Bytecisco respectively. The islands are numbered from 1 to n, while the bridges from 1 to m. The following lines specify the bridges. The line no.($n+1$) contains four integers $a_i,b_i,l_i,p_i$ ($1\le l_i,p_i \le 1000$), separated by single spaces. These denote that the bridge no. $i$ connects the islands no. $a$ and $b$. The opposing wind speeds are when one goes moves from to , and if one goes from $a$ to $b$.

    输出格式:

    If there is no route satisfying the requirements of the daring two riders, the first and only line of the standard output should hold the word NIE (no in Polish).

    Otherwise, the output should have two lines, specifying the least tiresome route over San Bytecisco.

    The first line should hold the maximum opposing wind speed for that route, i.e., the number we wish to minimize.

    The second line should hold integers, separated by single spaces, giving the numbers of successive bridges one crosses on the least tiresome route.

    Should there be more than one least tiresome route, your program can pick one arbitrarily.

    输入输出样例

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