水管

[题目描述]

这是一道难度一般的第二题,这绝对不是数学题也不是物理题.

我们有n个上方封顶且底面积相同的水箱,每个水箱有一个底部的海拔高度$p_i$和水箱高度$h_i$,开始时水箱可以认为是真空的(即没有水的部分是不占体积的,空气排不出去不会让水箱爆炸或者进不了水)

现在n个水箱之间有m条体积可以忽略不计的水管,第i条水管连接第$u_i$个水箱的$a_i$高度的位置(相对高度,即绝对高度应该为$p_{u_i}+a_i$)和第$v_i$个水箱的$b_i$高度的位置(同理),保证n个水箱联通,保证不会两个水箱的顶部高度相同.

现在我们向1号水箱里缓慢地灌水,在没有任何抽水机的情况下,水会逐渐填充满所有的水箱,保证水的流动满足基本的压强原理.

求水箱依次被填满的顺序.

[输入格式]

第一行两个整数表示n,m

第2~n+1行每行两个整数,第i+1行表示$p_i$和$h_i$

第n+2~n+m+1行每行四个整数,表示一根水管

分别代表$u_i$,$a_i$,$v_i$和$b_i$

[输出格式]

一行n个正整数表示一个排列

表示水箱被充满的顺序

[数据范围]

对于100%的数据,保证$1\leq n\leq 100000,n-1\leq m \leq 200000$

$0\leq p_i,h_i\leq 10^9,1\leq u_i,v_i\leq n,0\leq a_i\leq h_{u_i},0\leq b_i\leq h_{v_i}$

//这题最低要求可并堆…暂时废掉

//不对好像是我zz了

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注