bzoj#P2042. [2009国家集训队]Will的烦恼

[2009国家集训队]Will的烦恼

题目描述

大家小时候应该都喜欢自己动手做一些小制作,Will 也是这样的。Will 还记得他小时候喜欢用色卡纸剪剪贴贴弄出一些看起来很奇怪的东西,而自己却好像做出了件艺术品似的满心的欢喜。说真的,偶尔翻翻自己小时候的东西,想想小时候的事,真是一件非常温馨的事。这几天,Will 决定重温一下小时候的记忆。色卡纸显然缺乏立体感,于是 Will 找来了一大摞的彩绳和一些绳环(用来系绳子),准备用这些彩绳和绳环做一个大大的艺术品。一共有 NN 个绳环和 MM 根彩绳,方便起见,绳环从 11NN 分别编号,彩绳则从 11MM 分别编号。编号为 ii 的彩绳有一个长度 CiC_i 和一个美丽程度 DiD_i,并且只能连接两个特定的绳环:绳环 XiX_i 和绳环 YiY_i。Will 会按照一定的次序将彩绳依次系到绳环上。由于 Will 希望制作一个大大的艺术品,所以当一条彩绳连接特定的绳环之后,Will 会找出所有包含这条彩绳的彩绳圈,然后将每个彩绳圈中长度最短的那条彩绳,从绳环上取下来放到一边。如果有多条最短的彩绳,喜欢新事物的 Will 会将其中(指那些长度最短的彩绳)最早系到绳环上的那条彩绳取下来。最后,连在绳环上的彩绳就与绳环一起,组成了一个大大的艺术品咯!Will 保证,所有绳 环最后都会连在一起。艺术品上所有绳子美丽程度的和,就是这件大大的艺术品的美丽程度。Will 当然希望他的艺术品显得更漂亮些了,所以他希望艺术品的美丽程度能够最大化。显然,按不同的顺序系彩绳,会制作出不同的艺术品。这里不妨把系彩绳的顺序称为一个制作艺术品的方案,不难发现,一个方案可以简单的用一个 11MM 的排列来表示。Will 记得,他小时候总是会按照方案的字典序,从字典序最小的方案开始,一个方案接着一个方案的尝试,最后找出能做出最美丽艺术品的方案。不过,现在 Will 长大了,他望着面前一大摞的彩绳,猛然意识到,这回他似乎需要尝试很久很久……Will 需要你的帮助。请你帮 Will 找出,他将最早尝试的,并且能够做出最美丽艺术品的方案。说明一个绳环可以系上任意数量的彩绳。

所谓彩绳圈,指的是一个长度不小于 22 的彩绳编号的序列 (A1,A2,,An)(A_1,A_2,\ldots,A_n),满足任意元素均不相同,且对应存在一个同样长度为 NN,元素互不相同的绳环编号的序列 (B1,B2,,Bn)(B1,B2,\ldots,Bn),满足对于任意整数 i[1,n)i\in [1,n),彩绳 AiA_i 连接绳环 BiB_iBi+1B_i+1,特别的,彩绳 AnA_n 连接绳环 BnB_nB1B_1。对于一个方案 PP,即一个 11MM 的排列 (P1,P2,,PM)(P_1,P_2,\ldots,P_M),表示第 ii 个系到绳环上的彩绳,就是编号为 PiP_i 的彩绳。对于两个方案 PPQQ,如果 PP 的字典序小于 QQ,则一定存在一个 ii,使得 PiP_i (?)。

输入格式

共有 M+1M+1 行。
11 行两个正整数 NNMM,分别表示绳环和彩绳的数量。第 22M+1M+1 行,每行四个正整数。
i+1i+1 行描述编号为 ii 的彩绳的信息,四个整数依次为 Xi,Yi,Ci,DiX_i,Y_i,C_i,D_i。保证 XiX_iYiY_i 不会相同。

输出格式

共一行 MM 个整数。MM 个整数用 M1M-1 个空格隔开,表示一个方案。输出信息应该是一个 11MM 的排列。

样例输入

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

样例输出

1 2 4 3

样例解释

Will 首先会尝试方案 (1,2,3,4)(1,2,3,4),但是这个方案制作出的艺术品的美丽程度是 33,并不是最优的。 在样例给出的方案中,最后留下的彩绳是 22 号彩绳和 33 号彩绳,美丽程度是 2+3=52+3=5。 样例给出的答案经过评分能够得到 1010 分。

数据规模与约定

对于 10%10\% 的数据满足 N=5N = 5M=8M = 8
对于 30%30\% 的数据满足 N30N \leq 30M60M \leq 60
对于 60%60\% 的数据满足 N200N \leq 200M300M \leq 300
对于 70%70\% 的数据满足 N1500N \leq 1500M3×103M \leq 3\times10^3
对于 100%100\% 的数据满足 N5×104N \leq 5\times10^4M105M \leq 10^51Xi,YiN1 \leq X_i, Y_i \leq N1Ci1091 \leq C_i \leq 10^91Di1051 \leq D_i \leq 10^5

题目来源

版权所有者:吴翼