{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv align\u003d\"left\"\u003e给定由节点和管道组成的网络;管道连接节点。某种物质可以通过管道流动,任何管道中的流速不超过该管道的容量。\u003cbr\u003e物质不能在节点中积累。但是它在第一个节点中以非负速度被产生,并在最后一个节点以相同速度被消耗。\u003cbr\u003e给定了网络中一些管道的子集。您需要启动网络中物质的运动,并且您的运动必须完全填满给定子集的管道。第一个节点中产生物质的速度必须是最小的。\u003cbr\u003e计算这个速度并展示物质运动的场景。\u003cbr\u003e请记住,物质不能在网络的节点中积累。\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003e输入\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e输入的第一行包含两个正整数 N (1≤N≤100) 和 M - 节点和管道的数量。\u003cbr\u003e接下来有 M 行:每行包含四个整数 Ui, Vi, Zi, Ci;这些数字用空格分隔。Ui 是第 i 条管道的起点,Vi 是终点,Zi 是第 i 条管道的容量 (1≤Zi≤10^5),Ci 是 1 表示第 i 条管道必须完全填满,否则为 0。\u003cbr\u003e任意一对节点只能通过一条管道连接。如果从节点 A 到节点 B 有一条管道,那么从 B 到 A 就没有管道。没有一个节点与自身连接。\u003cbr\u003e没有连接节点编号为 1 和 N 的管道。物质只能从管道的起点流向终点。\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003e输出\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e在输出的第一行写一个整数 - 它应该是第一个节点中产生物质的最小速度。\u003cbr\u003e在第二行写 M 个整数 - 第 i 个数字应该是第 i 条管道的流速 (管道的编号与输入相同)。\u003cbr\u003e如果无法填满给定的子集,则写入 \"Impossible\"。\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003e示例测试\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e输入\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e输入 1: \u003cbr\u003e4 4 \u003cbr\u003e1 2 2 0 \u003cbr\u003e2 4 1 1 \u003cbr\u003e1 3 2 1 \u003cbr\u003e3 4 3 0 \u003cbr\u003e输入 2: \u003cbr\u003e4 4 \u003cbr\u003e1 2 1 0 \u003cbr\u003e2 4 2 1 \u003cbr\u003e1 3 3 1 \u003cbr\u003e3 4 2 0 \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e输出\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e输出 1: \u003cbr\u003e3 \u003cbr\u003e1 1 2 2 \u003cbr\u003e输出 2: \u003cbr\u003eImpossible \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003chr\u003e\u003c/div\u003e\u003ctable align\u003d\"left\" cellspacing\u003d\"7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003e作者:\u003c/td\u003e\u003ctd\u003e Dmitry Orlov \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e来源:\u003c/td\u003e\u003ctd\u003e Saratov ST team Spring Contest #1 \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e日期:\u003c/td\u003e\u003ctd\u003e 18.05.2003 \u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e \u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\n\u003c/div\u003e"}}]}