#P50585. 「POI2010」桥 Bridges
「POI2010」桥 Bridges
题目描述
译自 POI 2010 Stage 3. Day 2「Bridges」
给定一个 个点的无向图,每条边的两个方向各有一个权值,求一条从 号点出发,恰经过所有边一次并回到 号点的路线,使得权值的最大值最小。
输入格式
第一行两个整数 ,分别表示点的数量和边的数量。点从 到 编号,边从 到 编号。
接下来 行每行有四个整数 ,表示第 条边连接 ,且从 到 的权值为 ,从 到 的权值为 。
输出格式
如果原图不存在这样的路线,输出 NIE
。否则,应该输出两行,第一行表示路线中权值最大值的最小值,第二行有 个整数,依次表示你选择的路线的边。如果有多条这样的路线,可以输出任意一条。
样例
4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
4
4 3 2 1
最优路线为 ,最大权值为 。
数据范围与提示
对于 的数据, 。
Translated & SPJ by vincent163