← 返回题目列表

Codeforces · 68/C

C. 同步相加速器

中文机器翻译题面 查看原题

对于一些实验,小 Petya 需要同步相加速器。他已经拿到了装置,剩下的就是设置燃料供应了。燃料来自编号为 1 到 n 并通过管道连接的节点系统。管道从每个编号较小的节点到每个编号较大的节点。燃料只能从编号较小的节点到编号较大的节点的方向流经管道。任何数量的燃料都可以通过第一个节点进入,最后一个节点直接连接到同步相加速器。众所周知,每条管道都具有三个属性:应通过它的最小燃料量、可能通过它的最大燃料量以及管道启动成本。如果 cij 单位的燃料(cij > 0)从节点 i 流向节点 j,则将花费 aij + cij2 tugriks(aij 是管道激活的成本),如果燃料不流经管道,则不花费任何费用。每条管道只能流过整数单位的燃料。

对管道的最小和最大燃料容量的限制始终存在,不仅在其处于活动状态时。您可以假设当且仅当通过管道的流量严格大于零时管道处于活动状态。

Petya 不希望管道系统过载,因此他想找到进入第一个节点后可以到达同步相加速器的最小燃料量。除此之外,他还想给赞助商留下深刻的印象,因此通过每个管道的燃料费用必须尽可能大。

输入

第一行包含整数 n (2 ≤ n ≤ 6),表示节点数。接下来的 n(n - 1) / 2 行包含五个整数 s、f、l、h、a,它们描述管道 - 管道的第一个节点、管道的第二个节点、可以流过管道的最小和最大燃料量以及激活成本。 (1 ≤ s < f ≤ n,0 ≤ l ≤ h ≤ 5,0 ≤ a ≤ 6)。保证对于具有不同编号的每一对节点,在输入中描述的它们之间恰好有一个管道。

输出

在第一行输出两个空格分隔的数字:可以流入同步相加速器的最小可能燃料量,以及为了使该燃料量到达同步相加速器而需要支付的最大可能金额。如果没有足够的燃料可以到达同步相加速器,则输出“-1 -1”。

流入同步相加速器的燃料量不一定是正值。如果每个管道的最小约束都等于零,则它可以等于零。

示例

输入 #1

2
1 2 1 2 3

输出 #1

1 4

输入 #2

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

输出 #2

-1 -1

输入 #3

4
1 2 0 2 1
2 3 0 2 1
1 3 0 2 6
1 4 0 0 1
2 4 0 0 0
3 4 2 3 0

输出 #3

2 15

输入#4

3
1 2 0 2 1
1 3 1 2 1
2 3 1 2 1

输出#4

2 6

注意

在第一个测试中,我们可以将 1 或 2 单位燃料从节点 1 传递到节点 2。最小可能数量为 1,其成本为 a12 + 12 = 4。

在第二次测试中,从节点1到节点2最多可以通过2个单元,而从节点2到节点3则必须至少通过3个单元。这是不可能的。

在第三个测试中,最小可能数量为 2。您可以通过两条不同的路径传递每个单位的燃料:1->2->3->4 或 1->3->4。如果使用第一个路径两次,则花费 a12 + 22 + a23 + 22 + a34 + 22=14。如果使用第二条路径两次,则花费 a13 + 22 + a34 + 22=14。然而,如果您使用每条路径(允许一单位燃料通过管道 1->2、2->3、1->3,并且两个单位通过管道 3->4),则将花费 a12 + 12 + a23 + 12 + a13 + 12 + a34 + 22=15,这是最大可能的成本。

另请注意,由于没有燃料从节点 1 流向节点 4,因此该管道的激活成本不会添加到答案中。