{"trustable":true,"sections":[{"title":"题目描述","value":{"format":"MD","content":"这是一道模板题。\r\n\r\n给定 $ n $ 个点,$ m $ 条有向边,给定每条边的容量,求从点 $ s $ 到点 $ t $ 的最大流。"}},{"title":"输入格式","value":{"format":"MD","content":"第一行四个整数 $ n, m, s, t $。 \r\n接下来的 $ m $ 行,每行三个整数 $ u , v , c $,表示起点为 $ u $,终点为 $ v $,流量为 $ c $ 的一条有向边。"}},{"title":"输出格式","value":{"format":"MD","content":"输出点 $ s $ 到点 $ t $ 的最大流。"}},{"title":"样例 1","value":{"format":"MD","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\u003e7 14 1 7\n1 2 5\n1 3 6\n1 4 5\n2 3 2\n2 5 3\n3 2 2\n3 4 3\n3 5 3\n3 6 7\n4 6 5\n5 6 1\n6 5 1\n5 7 8\n6 7 7\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"样例 2","value":{"format":"MD","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\u003e10 16 1 2\n1 3 2\n1 4 2\n5 2 2\n6 2 2\n3 5 1\n3 6 1\n4 5 1\n4 6 1\n1 7 2147483647\n9 2 2147483647\n7 8 2147483647\n10 9 2147483647\n8 5 2\n8 6 2\n3 10 2\n4 10 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"数据范围与提示","value":{"format":"MD","content":"$1\\leqslant n \\leqslant 1200, 1\\leqslant m \\leqslant 120000, 1\\leqslant c \\leqslant 2^{31}-1 $。\r\n\r\n保证答案不超过$ 2^{31}-1 $。\r\n\r\n常用网络流算法的复杂度为 $ O(n ^ 2 m) $,请尽量优化算法。"}}]}