33OJ
登录 注册

#P3511. [POI 2010] MOS-Bridges

    ID: 4352 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>2010二分POI(波兰)网络流Special Judge欧拉回路

[POI 2010] MOS-Bridges

题目描述

San Bytecisco 是一个风景优美的沿海小镇。

它由一些小而人口稠密的岛屿组成,编号从 11 到 nn。

某些岛屿之间通过桥梁连接,用于双向的道路交通。

每对岛屿之间最多有一座桥。

这些岛屿之间连接的桥梁使得每个岛屿都可以到达其他岛屿。

Byteasar 和 Bytie 正计划在 San Bytecisco 骑自行车旅行。

他们将从 11 号岛出发。

他们打算访问每个岛屿,同时每座桥只经过一次,并在旅行结束时回到出发地,即 11 号岛。

作为经验丰富的骑手,他们预计会遇到一些严重的麻烦……风!

毕竟,沿海地区风很大,尤其是在岛屿之间的桥上。显然,根据风速和方向,风使得跨越桥梁面临不同程度上的困难。

为了简单起见,我们假设每座桥的任意一个跨越方向遭到的逆风的速度是恒定的。

Byteasar 和 Bytie 决定将遭到的逆风的最大速度作为路线疲劳程度的衡量标准。帮助 Byteasar 和 Bytie 找到他们想要的路线,使得这条路线的疲劳程度最小。

输入格式

标准输入的第一行有两个用空格分隔的整数:nn 和 mm(2≤n≤10002 \le n \le 1000,1≤m≤20001 \le m \le 2000),分别表示 San Bytecisco 的岛屿数量和桥梁数量。岛屿编号从 11 到 nn,桥梁编号从 11 到 mm。接下来的 mm 行给出了桥梁。第 i+1i+1 行包含四个用空格分隔的整数 ai,bi,li,pia_i,b_i,l_i,p_i(1≤li,pi≤10001 \le l_i,p_i \le 1000),表示第 ii 号桥连接了第 aia_i 号和第 bib_i 号岛屿。当从 aia_i 到 bib_i 移动时遭到的逆风的速度为 lil_i,而从 bib_i 到 aia_i 移动时遭到的逆风的速度为 pip_i。

输出格式

如果没有满足这两位勇敢骑手要求的路线,标准输出的第一行应为单词 NIE(波兰语中的“不”)。

否则,输出应有两行,指定 San Bytecisco 上最不疲劳的路线。

第一行应包含该路线遭到的逆风的最大速度,即我们希望最小化的数字。

第二行应包含 mm 个整数,用空格分隔,表示在最不疲劳的路线中依次经过的桥梁编号。

如果有多条最不疲劳的路线,你可以输出任意一条。

4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
4
4 3 2 1

提示

2≤n≤10002 \le n \le 1000,1≤m≤20001 \le m \le 2000,1≤ai,bi≤n1 \le a_i,b_i \le n,ai≠bia_i\neq b_i,1≤li,pi≤10001 \le l_i,p_i \le 1000。

题面翻译由 ChatGPT-4o 提供。