{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003eAs you know, all the computers used for ACM contests must be identical, so the participants compete on equal terms. That is why all these computers are historically produced at the same factory.\u003c/p\u003e\u003cp\u003eEvery ACM computer consists of P parts. When all these parts are present, the computer is ready and can be shipped to one of the numerous ACM contests.\u003c/p\u003e\u003cp\u003eComputer manufacturing is fully automated by using \u003ci\u003eN\u003c/i\u003e various machines. Each machine removes some parts from a half-finished computer and adds some new parts (removing of parts is sometimes necessary as the parts cannot be added to a computer in arbitrary order). Each machine is described by its performance (measured in computers per hour), input and output specification.\u003c/p\u003e\u003cp\u003eInput specification describes which parts must be present in a half-finished computer for the machine to be able to operate on it. The specification is a set of \u003ci\u003eP\u003c/i\u003e numbers 0, 1 or 2 (one number for each part), where 0 means that corresponding part must not be present, 1 — the part is required, 2 — presence of the part doesn\u0027t matter.\u003c/p\u003e\u003cp\u003eOutput specification describes the result of the operation, and is a set of \u003ci\u003eP\u003c/i\u003e numbers 0 or 1, where 0 means that the part is absent, 1 — the part is present.\u003c/p\u003e\u003cp\u003eThe machines are connected by very fast production lines so that delivery time is negligibly small compared to production time.\u003c/p\u003e\u003cp\u003eAfter many years of operation the overall performance of the ACM Computer Factory became insufficient for satisfying the growing contest needs. That is why ACM directorate decided to upgrade the factory.\u003c/p\u003e\u003cp\u003eAs different machines were installed in different time periods, they were often not optimally connected to the existing factory machines. It was noted that the easiest way to upgrade the factory is to rearrange production lines. ACM directorate decided to entrust you with solving this problem.\u003c/p\u003e\u003c/div\u003e\n\n题目大意:\n生产电脑的工厂将一台电脑分成P个部件来进行流水线生产组装,有N个生产车间,每个车间可以将一个半成品电脑添加某些部件,使之成为另一个半成品电脑或者成为一台完好的电脑,且每个车间有一个效率,即在单位时间内可以将K个半成品组装为另外K个半成品或者完好的电脑。每个车间在组装完成之后,都将组装后的半成品送到另外一个车间,成品直接送到成品区。 \n 对于每个车间,有加工前入口和加工后入口,每个口有P个部件表示,每个部件使用0,1或者2来表示状态,1表示一定需要有入/出的材料,0表示不能有入/出的材料,2表示可能有入的材料。如果一个机器入口的P个部件全是0,代表这是起始机器,如果一个机器出口全是1,那么代表电脑加工完成。求这个工厂单位时间内最多可以产出多少台电脑。"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003eInput file contains integers \u003ci\u003eP\u003c/i\u003e \u003ci\u003eN\u003c/i\u003e, then \u003ci\u003eN\u003c/i\u003e descriptions of the machines. The description of \u003ci\u003ei\u003c/i\u003eth machine is represented as by 2 \u003ci\u003eP\u003c/i\u003e + 1 integers \u003ci\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e,1\u003c/sub\u003e \u003ci\u003eSi\u003c/i\u003e\u003csub\u003e,2\u003c/sub\u003e...\u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e,\u003ci\u003eP\u003c/i\u003e\u003c/sub\u003e \u003ci\u003eD\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e,1\u003c/sub\u003e \u003ci\u003eD\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e,2\u003c/sub\u003e...\u003ci\u003eD\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e,\u003ci\u003eP\u003c/i\u003e\u003c/sub\u003e, where \u003ci\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e specifies performance, \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e,\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e — input specification for part \u003ci\u003ej\u003c/i\u003e, \u003ci\u003eD\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003csub\u003e,\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e — output specification for part \u003ci\u003ek\u003c/i\u003e.\u003c/p\u003e\u003cp\u003e1 ≤ \u003ci\u003eP\u003c/i\u003e ≤ 10, 1 ≤ \u003ci\u003eN \u003c/i\u003e≤ 50, 1 ≤ \u003ci\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 10000 \u003c/p\u003e\u003c/div\u003e\n\n第一行输入两个数P N,表示一台电脑分成P个部件,有N个生产车间。\n接下来N行,每行有1 + 2*P个数字,第一个数字Q,代表当前生产车间每单位时间最多能加工Q个部件。接下来P个数字代表加工入口时部件需要的状态,最后P个数字代表加工出口后部件的状态。\n\u003cp\u003e1 ≤ \u003ci\u003eP\u003c/i\u003e ≤ 10, 1 ≤ \u003ci\u003eN \u003c/i\u003e≤ 50, 1 ≤ \u003ci\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 10000 \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003eOutput the maximum possible overall performance, then \u003ci\u003eM\u003c/i\u003e — number of connections that must be made, then \u003ci\u003eM\u003c/i\u003e descriptions of the connections. Each connection between machines \u003ci\u003eA\u003c/i\u003e and \u003ci\u003eB\u003c/i\u003e must be described by three positive numbers \u003ci\u003eA\u003c/i\u003e \u003ci\u003eB\u003c/i\u003e \u003ci\u003eW\u003c/i\u003e, where \u003ci\u003eW\u003c/i\u003e is the number of computers delivered from \u003ci\u003eA\u003c/i\u003e to \u003ci\u003eB\u003c/i\u003e per hour.\u003c/p\u003e\u003cp\u003eIf several solutions exist, output any of them.\u003c/p\u003e\u003c/div\u003e\n\n请输出单位时间内最多能造出来的电脑数量并且输出详细方案。\n第一行输出2个数,第一个数输出单位时间内最多能造出来的电脑数量,第二个数字输出工厂之间的连接数量M。\n接下来M行,输出连接的两个工厂编号,以及传输的部件台数。\n如果有多种解决方案,输出其中之一即可。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\u003cb\u003eSample input 1\u003c/b\u003e\n3 4\n15 0 0 0 0 1 0\n10 0 0 0 0 1 1\n30 0 1 2 1 1 1\n3 0 2 1 1 1 1\n\u003cb\u003eSample input 2\u003c/b\u003e\n3 5\n5 0 0 0 0 1 0\n100 0 1 0 1 0 1\n3 0 1 0 1 1 0\n1 1 0 1 1 1 0\n300 1 1 2 1 1 1\n\u003cb\u003eSample input 3\u003c/b\u003e\n2 2\n100 0 0 1 0\n200 0 1 1 1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\u003cb\u003eSample output 1\u003c/b\u003e\n25 2\n1 3 15\n2 3 10\n\u003cb\u003eSample output 2\u003c/b\u003e\n4 5\n1 3 3\n3 5 3\n1 2 1\n2 4 1\n4 5 1\n\u003cb\u003eSample output 3\u003c/b\u003e\n0 0\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"第一个样例最多生产25台,第一个车间生产15台给第三车间,第二个车间生产10台给第三车间,第三车间拿25台生产成品。\n第二个样例最多生产4台,第一个车间生产3台给第三车间,第三车间加工3台给第五车间,第一车间生产1台给第二车间,第二车间加工1台给第四车间,第四车间加工1台给第五车间,第五车间拿4台加工出成品。"}}]}