{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"一个电力网络由节点(发电站、用户和调度器)通过电力输送线连接而成。节点u可以被供给一定数量的电力s(u) \u003e\u003d 0,可以产生一定数量的电力0 \u003c\u003d p(u) \u003c\u003d p\u003csub\u003emax\u003c/sub\u003e(u),可以消耗一定数量的电力0 \u003c\u003d c(u) \u003c\u003d min(s(u),c\u003csub\u003emax\u003c/sub\u003e(u)),并且可以传送一定数量的电力d(u)\u003ds(u)+p(u)-c(u)。以下限制适用:对于任何发电站,c(u)\u003d0;对于任何用户,p(u)\u003d0;对于任何调度器,p(u)\u003dc(u)\u003d0。在网络中从节点u到节点v最多有一条电力输送线(u,v),它传送由u传送到v的一定数量的电力0 \u003c\u003d l(u,v) \u003c\u003d l\u003csub\u003emax\u003c/sub\u003e(u,v)。让Con\u003dΣ\u003csub\u003eu\u003c/sub\u003ec(u)表示网络中消耗的电力总量。问题是计算Con的最大值。\n\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/1c1354d5a7c820146d570a7875b230b3?v\u003d1704941339\"\u003e\u003c/center\u003e\n\u003cbr\u003e图1中有一个例子。发电站u的标签x/y表示p(u)\u003dx和p\u003csub\u003emax\u003c/sub\u003e(u)\u003dy。用户u的标签x/y表示c(u)\u003dx和c\u003csub\u003emax\u003c/sub\u003e(u)\u003dy。电力输送线(u,v)的标签x/y表示l(u,v)\u003dx和l\u003csub\u003emax\u003c/sub\u003e(u,v)\u003dy。消耗的电力为Con\u003d6。请注意,网络还有其他可能的状态,但Con的值不会超过6。"}},{"title":"输入","value":{"format":"HTML","content":"输入中有几组数据。每组数据编码了一个电力网络。它以四个整数开头:0 \u003c\u003d n \u003c\u003d 100(节点数),0 \u003c\u003d np \u003c\u003d n(发电站数),0 \u003c\u003d nc \u003c\u003d n(用户数)和0 \u003c\u003d m \u003c\u003d n^2(电力输送线数)。接下来是m个数据三元组(u,v)z,其中u和v是节点标识符(从0开始),0 \u003c\u003d z \u003c\u003d 1000是l\u003csub\u003emax\u003c/sub\u003e(u,v)的值。然后是np个双数(u)z,其中u是发电站的标识符,0 \u003c\u003d z \u003c\u003d 10000是p\u003csub\u003emax\u003c/sub\u003e(u)的值。数据集以nc个双数(u)z结束,其中u是用户的标识符,0 \u003c\u003d z \u003c\u003d 10000是c\u003csub\u003emax\u003c/sub\u003e(u)的值。所有输入数字都是整数。除了(u,v)z三元组和(u)z双数不包含空格外,输入中可以自由出现空格。输入数据以文件结束,并且是正确的。"}},{"title":"输出","value":{"format":"HTML","content":"对于输入中的每组数据,程序在标准输出上打印出对应网络中可以消耗的最大电力量。每个结果都是整数值,并且从新行的开头打印出来。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20\r\n7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7\r\n (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5\r\n (0)5 (1)2 (3)2 (4)1 (5)4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\r\n6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"示例输入包含两组数据。第一组数据编码了一个有2个节点的网络,发电站0的pmax(0)\u003d15,用户1的cmax(1)\u003d20,还有两条电力输送线,lmax(0,1)\u003d20和lmax(1,0)\u003d10。Con的最大值为15。第二组数据编码了图1中的网络。"}}]}