\u5982\u679c\u8bf4\u6700\u5927\u6d41\u662f\u201c\u5982\u4f55\u7528\u6700\u5feb\u7684\u901f\u5ea6\u628a\u6c34\u4eceA\u9001\u5230B\u201d，\u90a3\u4e48\u6700\u5c0f\u5272\u5c31\u662f\u201c\u5982\u4f55\u7528\u6700\u5c11\u7684\u4ee3\u4ef7\u5207\u65adA\u5230B\u7684\u6240\u6709\u901a\u8def\u201d\u2014\u2014\u5b83\u7528\u4e00\u5f20\u7f51\u7edc\u548c\u4e00\u628a\u201c\u526a\u5200\u201d，\u56de\u7b54\u4e86\u6240\u6709\u963b\u65ad\u95ee\u9898\u7684\u6700\u4f18\u89e3\u3002<\/p>\n
\u5047\u8bbe\u4f60\u662f\u4e00\u540d\u6307\u6325\u5b98，\u654c\u519b\u6709\u4e00\u6761\u4ece\u540e\u65b9\u57fa\u5730\u5230\u524d\u7ebf\u7684\u8865\u7ed9\u7ebf\u7f51\u7edc\u2014\u2014\u591a\u6761\u9053\u8def\u4ea4\u7ec7，\u56db\u901a\u516b\u8fbe\u3002\u4f60\u7684\u4efb\u52a1\u662f：\u70b8\u6389\u6700\u5c11\u7684\u9053\u8def（\u6216\u8005\u8bf4\u82b1\u8d39\u6700\u5c0f\u7684\u4ee3\u4ef7），\u8ba9\u8865\u7ed9\u5f7b\u5e95\u65e0\u6cd5\u9001\u8fbe\u524d\u7ebf\u3002\u6bcf\u6761\u9053\u8def\u7684\u70b8\u6bc1\u6210\u672c\u4e0d\u540c，\u4f60\u8be5\u600e\u4e48\u9009？<\/p>\n
\u8fd9\u4e2a\u95ee\u9898\u5728\u7b97\u6cd5\u7ade\u8d5b\u4e2d\u6709\u4e00\u4e2a\u6807\u51c6\u7684\u6570\u5b66\u6a21\u578b\u2014\u2014\u6700\u5c0f\u5272（Minimum Cut）\u00a0\u3002\u800c\u201c\u6700\u5927\u6d41\u7b49\u4e8e\u6700\u5c0f\u5272\u201d\u8fd9\u6761\u5b9a\u7406，\u5219\u662f\u89e3\u51b3\u8fd9\u7c7b\u95ee\u9898\u7684\u6838\u5fc3\u6b66\u5668\u3002<\/p>\n
\u4f60\u7b2c\u4e00\u5929\u63a5\u624b\u4e09\u9e7f\u725b\u5976\u516c\u53f8\u5c31\u53d1\u751f\u4e86\u4e00\u4ef6\u5012\u9709\u7684\u4e8b\u60c5：\u516c\u53f8\u4e0d\u5c0f\u5fc3\u53d1\u9001\u4e86\u4e00\u6279\u6709\u4e09\u805a\u6c30\u80fa\u7684\u725b\u5976\u3002\u9001\u8d27\u7f51\u5f88\u5927，\u5173\u7cfb\u590d\u6742，\u574f\u725b\u5976\u5df2\u7ecf\u8fdb\u5165\u4e86\u8fd9\u4e2a\u7f51\u7edc\u3002\u4f60\u7684\u4efb\u52a1\u662f，\u5728\u4fdd\u8bc1\u574f\u725b\u5976\u4e0d\u9001\u5230\u96f6\u552e\u5546（\u8282\u70b9N）\u7684\u524d\u63d0\u4e0b，\u505c\u6b62\u67d0\u4e9b\u8fd0\u8f93\u5361\u8f66，\u4f7f\u635f\u5931\u6700\u5c0f\u2014\u2014\u540c\u65f6，\u5728\u635f\u5931\u6700\u5c0f\u7684\u524d\u63d0\u4e0b，\u8fd8\u8981\u8ba9\u505c\u6b62\u7684\u5361\u8f66\u6570\u91cf\u6700\u5c11\u3002<\/p>\n
\u8fd9\u5c31\u662f\u6d1b\u8c37 P1344 [USACO4.4] \u8ffd\u67e5\u574f\u725b\u5976 Pollutant Control\u00a0\u8981\u89e3\u51b3\u7684\u95ee\u9898\u3002<\/p>\n
\u201c\u5982\u679c\u8bf4\u7f51\u7edc\u6d41\u662f\u56fe\u8bba\u4e2d\u7684\u2018\u6c34\u5229\u5de5\u7a0b\u2019，\u90a3\u4e48\u6700\u5c0f\u5272\u5c31\u662f\u5b83\u7684\u2018\u5b9a\u5411\u7206\u7834\u2019\u2014\u2014\u4f60\u4e0d\u9700\u8981\u5173\u5fc3\u6c34\u600e\u4e48\u6d41，\u53ea\u9700\u8981\u77e5\u9053\u5728\u54ea\u91cc\u5207\u65ad\u6700\u5212\u7b97\u3002\u201d<\/p>\n
\u5728\u9605\u8bfb\u672c\u6587\u4e4b\u524d，\u5efa\u8bae\u4f60\u719f\u6089\u4ee5\u4e0b\u6982\u5ff5：<\/p>\n
\u6d41\u7f51\u7edc（Flow Network）\u00a0：\u4e00\u4e2a\u6709\u5411\u56fe，\u6bcf\u6761\u8fb9\u6709\u5bb9\u91cf（capacity），\u6e90\u70b9（source）\u4ea7\u751f\u6d41\u91cf，\u6c47\u70b9（sink）\u63a5\u6536\u6d41\u91cf\u3002<\/p>\n<\/li>\n
\u6700\u5927\u6d41（Maximum Flow）\u00a0：\u4ece\u6e90\u70b9\u5230\u6c47\u70b9\u80fd\u8f93\u9001\u7684\u6700\u5927\u6d41\u91cf\u3002<\/p>\n<\/li>\n
\u589e\u5e7f\u8def（Augmenting Path）\u00a0：\u5728\u6b8b\u7559\u7f51\u7edc\u4e2d\u4ece\u6e90\u70b9\u5230\u6c47\u70b9\u7684\u4e00\u6761\u8def\u5f84，\u6cbf\u5b83\u53ef\u4ee5\u589e\u52a0\u6d41\u91cf\u3002<\/p>\n<\/li>\n
DFS\u4e0eBFS：Dinic\u7b97\u6cd5\u7684\u57fa\u7840\u904d\u5386\u624b\u6bb5\u3002<\/p>\n<\/li>\n
\u65f6\u95f4\u590d\u6742\u5ea6\u5206\u6790：\u7406\u89e3\u7b97\u6cd5\u7684\u6e10\u8fd1\u590d\u6742\u5ea6\u3002<\/p>\n<\/li>\n
\u5728\u4e00\u4e2a\u6d41\u7f51\u7edc\u4e2d，\u4e00\u4e2a\u00a0\u5272（Cut）\u00a0\u5c31\u662f\u628a\u6240\u6709\u8282\u70b9\u5206\u6210\u4e24\u4e2a\u96c6\u5408\u2014\u2014SS\u548cTT，\u6ee1\u8db3\u6e90\u70b9s\u2208S，\u6c47\u70b9t\u2208T\u3002<\/p>\n
\u5272\u7684\u00a0\u5bb9\u91cf（Capacity）\u00a0\u5b9a\u4e49\u4e3a：\u6240\u6709\u4eceS\u6307\u5411T\u7684\u8fb9\u7684\u5bb9\u91cf\u4e4b\u548c\u3002<\/p>\n
\u6362\u53e5\u8bdd\u8bf4，\u5272\u7684\u5bb9\u91cf\u5c31\u662f\u4f60\u4e3a\u4e86\u5207\u65ads\u5230t\u7684\u6240\u6709\u901a\u8def，\u9700\u8981\u201c\u526a\u6389\u201d\u7684\u90a3\u4e9b\u8fb9\u7684\u603b\u5bb9\u91cf\u3002<\/p>\n
\u6700\u5c0f\u5272（Minimum Cut）\u00a0，\u5c31\u662f\u5728\u6240\u6709\u53ef\u80fd\u7684\u5272\u4e2d，\u5bb9\u91cf\u6700\u5c0f\u7684\u90a3\u4e2a\u5272\u3002<\/p>\n
\u4e3a\u4ec0\u4e48\u6700\u5c0f\u5272\u91cd\u8981？\u56e0\u4e3a\u5b83\u56de\u7b54\u4e86\u4e00\u4e2a\u6838\u5fc3\u95ee\u9898：\u5207\u65ad\u6e90\u70b9\u5230\u6c47\u70b9\u7684\u6240\u6709\u8def\u5f84，\u6700\u5c11\u9700\u8981\u4ed8\u51fa\u591a\u5c11\u4ee3\u4ef7？<\/p>\n
\u8fd9\u6b63\u597d\u5bf9\u5e94\u4e86P1344\u7684\u7b2c\u4e00\u95ee\u2014\u2014\u201c\u4f7f\u574f\u725b\u5976\u65e0\u6cd5\u9001\u8fbe\u96f6\u552e\u5546\u7684\u6700\u5c0f\u7ecf\u6d4e\u635f\u5931\u201d\u3002<\/p>\n
\u60f3\u8c61\u4e00\u4e2a\u4f9b\u6c34\u7f51\u7edc：\u81ea\u6765\u6c34\u5382（\u6e90\u70b9）\u5411\u4f60\u5bb6（\u6c47\u70b9）\u4f9b\u6c34，\u4e2d\u95f4\u7ecf\u8fc7\u65e0\u6570\u7ba1\u9053\u548c\u6c34\u95f8\u3002\u73b0\u5728\u653f\u5e9c\u8981\u68c0\u4fee\u7ba1\u9053，\u9700\u8981\u5173\u95ed\u4e00\u4e9b\u6c34\u95f8\u8ba9\u4f60\u5bb6\u6682\u65f6\u505c\u6c34\u3002\u6bcf\u4e2a\u6c34\u95f8\u7684\u5173\u95ed\u6210\u672c\u4e0d\u540c\u2014\u2014\u6709\u7684\u95f8\u95e8\u9508\u4e86\u5f88\u96be\u5173（\u6210\u672c\u9ad8），\u6709\u7684\u5f88\u597d\u5173（\u6210\u672c\u4f4e）\u3002\u6700\u5c0f\u5272\u5c31\u662f\u544a\u8bc9\u4f60：\u5173\u54ea\u4e9b\u6c34\u95f8，\u65e2\u80fd\u8ba9\u6c34\u5b8c\u5168\u505c\u6389，\u53c8\u82b1\u6700\u5c11\u7684\u94b1\u3002<\/p>\n
\u8fd9\u5c31\u662f\u6700\u5c0f\u5272\u7684\u76f4\u89c9\u2014\u2014\u82b1\u6700\u5c11\u7684\u4ee3\u4ef7，\u5f7b\u5e95\u963b\u65ad\u3002<\/p>\n
\u6700\u5927\u6d41\u6700\u5c0f\u5272\u5b9a\u7406（Max-Flow Min-Cut Theorem）\u00a0\u662f\u7f51\u7edc\u6d41\u7406\u8bba\u4e2d\u6700\u6838\u5fc3\u7684\u5b9a\u7406\u4e4b\u4e00：<\/p>\n
\u5728\u4e00\u4e2a\u6d41\u7f51\u7edc\u4e2d，\u4ece\u6e90\u70b9\u5230\u6c47\u70b9\u7684\u6700\u5927\u6d41\u91cf，\u7b49\u4e8e\u6700\u5c0f\u5272\u7684\u5bb9\u91cf\u3002<\/p>\n
\u8fd9\u4e2a\u5b9a\u7406\u4e3a\u4ec0\u4e48\u6210\u7acb？\u76f4\u89c2\u4e0a\u53ef\u4ee5\u8fd9\u6837\u7406\u89e3：<\/p>\n
\u6700\u5927\u6d41\u4e0d\u53ef\u80fd\u5927\u4e8e\u6700\u5c0f\u5272：\u56e0\u4e3a\u6240\u6709\u4eces\u5230t\u7684\u6d41\u91cf\u90fd\u5fc5\u987b\u7ecf\u8fc7\u4efb\u610f\u4e00\u4e2a\u5272，\u800c\u5272\u7684\u5bb9\u91cf\u9650\u5236\u4e86\u80fd\u901a\u8fc7\u7684\u603b\u6d41\u91cf\u3002<\/p>\n<\/li>\n
\u6700\u5927\u6d41\u4e0d\u53ef\u80fd\u5c0f\u4e8e\u6700\u5c0f\u5272：\u5982\u679c\u6700\u5927\u6d41\u5c0f\u4e8e\u67d0\u4e2a\u5272\u7684\u5bb9\u91cf，\u8bf4\u660e\u7f51\u7edc\u8fd8\u6ca1\u6709\u88ab\u5145\u5206\u5229\u7528，\u53ef\u4ee5\u7ee7\u7eed\u589e\u5e7f\u3002<\/p>\n<\/li>\n<\/ul>\n
\u6240\u4ee5\u4e24\u8005\u5fc5\u7136\u76f8\u7b49\u3002<\/p>\n
\u4e25\u683c\u7684\u8bc1\u660e\u901a\u5e38\u5206\u4e24\u6b65：<\/p>\n
\u4efb\u610f\u6d41 \u2264 \u4efb\u610f\u5272\u7684\u5bb9\u91cf：\u5bf9\u4e8e\u4efb\u610f\u53ef\u884c\u6d41f\u548c\u4efb\u610f\u5272(S,T)，\u6d41\u7684\u503c\u7b49\u4e8e\u4eceS\u6d41\u51fa\u7684\u51c0\u6d41\u91cf，\u4e0d\u53ef\u80fd\u8d85\u8fc7\u5272\u7684\u5bb9\u91cf\u3002<\/p>\n<\/li>\n
\u5b58\u5728\u4e00\u4e2a\u6d41\u8fbe\u5230\u6700\u5c0f\u5272\u7684\u5bb9\u91cf：\u5f53\u7b97\u6cd5（\u5982Ford-Fulkerson）\u7ec8\u6b62\u65f6，\u6b8b\u7559\u7f51\u7edc\u4e2d\u4e0d\u5b58\u5728\u589e\u5e7f\u8def\u3002\u6b64\u65f6\u5b9a\u4e49S\u4e3a\u4ece\u6e90\u70b9\u80fd\u5230\u8fbe\u7684\u6240\u6709\u8282\u70b9，T\u4e3a\u5176\u4f59\u8282\u70b9，\u5219(S,T)\u662f\u4e00\u4e2a\u5272，\u4e14\u5176\u5bb9\u91cf\u6070\u597d\u7b49\u4e8e\u5f53\u524d\u6d41\u7684\u503c\u3002<\/p>\n<\/li>\n
\u56e0\u6b64，\u6700\u5927\u6d41 = \u6700\u5c0f\u5272\u3002<\/p>\n
\u8fd9\u4e2a\u5b9a\u7406\u6700\u5927\u7684\u5b9e\u7528\u4ef7\u503c\u5728\u4e8e：\u6c42\u6700\u5c0f\u5272，\u7b49\u4ef7\u4e8e\u6c42\u6700\u5927\u6d41\u3002<\/p>\n
\u4e5f\u5c31\u662f\u8bf4，\u6211\u4eec\u4e0d\u9700\u8981\u5355\u72ec\u8bbe\u8ba1\u4e00\u4e2a\u201c\u6c42\u6700\u5c0f\u5272\u201d\u7684\u7b97\u6cd5\u2014\u2014\u53ea\u9700\u8981\u8dd1\u4e00\u904d\u6700\u5927\u6d41（\u6bd4\u5982Dinic\u7b97\u6cd5），\u5f97\u5230\u7684\u6700\u5927\u6d41\u6570\u503c\u5c31\u662f\u6700\u5c0f\u5272\u7684\u5bb9\u91cf\u3002<\/p>\n
\u5728P1344\u4e2d，\u7b2c\u4e00\u95ee\u201c\u6700\u5c0f\u7684\u7ecf\u6d4e\u635f\u5931\u201d，\u5c31\u662f\u76f4\u63a5\u8dd1\u6700\u5927\u6d41\u7684\u7ed3\u679c\u3002<\/p>\n
P1344\u8981\u6c42\u8f93\u51fa\u4e24\u4e2a\u6574\u6570：<\/p>\n
C：\u6700\u5c0f\u7684\u635f\u5931（\u5373\u6700\u5c0f\u5272\u7684\u5bb9\u91cf）<\/p>\n<\/li>\n
T：\u5728\u635f\u5931\u6700\u5c0f\u7684\u524d\u63d0\u4e0b，\u6700\u5c11\u8981\u505c\u6b62\u7684\u5361\u8f66\u6570（\u5373\u6700\u5c0f\u5272\u4e2d\u5305\u542b\u7684\u8fb9\u6570）<\/p>\n<\/li>\n
\u7b2c\u4e00\u95ee\u5f88\u7b80\u5355\u2014\u2014\u76f4\u63a5\u5efa\u56fe\u8dd1\u6700\u5927\u6d41\u3002<\/p>\n
\u96be\u70b9\u5728\u7b2c\u4e8c\u95ee：\u6700\u5c0f\u5272\u53ef\u80fd\u6709\u591a\u79cd\u65b9\u6848，\u6211\u4eec\u8981\u4ece\u4e2d\u9009\u51fa\u8fb9\u6570\u6700\u5c11\u7684\u90a3\u4e00\u4e2a\u3002\u4e5f\u5c31\u662f\u8bf4，\u5728\u201c\u6700\u5c0f\u635f\u5931\u201d\u548c\u201c\u6700\u5c11\u505c\u8fd0\u5361\u8f66\u6570\u201d\u4e4b\u95f4，\u524d\u8005\u4f18\u5148\u7ea7\u66f4\u9ad8\u3002<\/p>\n
\u4e00\u4e2a\u76f4\u89c2\u7684\u60f3\u6cd5\u662f：\u5148\u8dd1\u4e00\u904d\u6700\u5927\u6d41\u6c42\u51fa\u6700\u5c0f\u5272\u7684\u5bb9\u91cf，\u7136\u540e\u628a\u6240\u6709\u8fb9\u7684\u5bb9\u91cf\u6539\u62101，\u518d\u8dd1\u4e00\u904d\u6700\u5927\u6d41，\u5f97\u5230\u6700\u5c11\u8fb9\u6570\u3002<\/p>\n
\u8fd9\u6837\u505a\u786e\u5b9e\u53ef\u884c，\u4f46\u8981\u8dd1\u4e24\u904d\u7f51\u7edc\u6d41，\u4ee3\u7801\u91cf\u5927\u3001\u5e38\u6570\u4e5f\u5927\u3002\u5728\u7b97\u6cd5\u7ade\u8d5b\u4e2d，\u6211\u4eec\u8ffd\u6c42\u66f4\u4f18\u96c5\u7684\u4e00\u6b21\u5efa\u56fe\u3001\u4e00\u6b21\u8dd1\u6d41\u7684\u89e3\u6cd5\u3002<\/p>\n
\u65e2\u7136\u8981\u540c\u65f6\u4f18\u5316\u4e24\u4e2a\u76ee\u6807\u2014\u2014\u4e3b\u76ee\u6807（\u635f\u5931\u6700\u5c0f）\u4f18\u5148\u7ea7\u9ad8\u4e8e\u8f85\u76ee\u6807（\u8fb9\u6570\u6700\u5c11）\u2014\u2014\u6211\u4eec\u53ef\u4ee5\u628a\u4e24\u4e2a\u76ee\u6807\u201c\u7f16\u7801\u201d\u5230\u540c\u4e00\u6761\u8fb9\u7684\u5bb9\u91cf\u4e2d\u3002<\/p>\n
\u5177\u4f53\u505a\u6cd5\u662f：\u5c06\u6bcf\u6761\u8fb9\u7684\u5bb9\u91cf\u4ece\u00a0w \u6539\u4e3a\u00a0w\u00d7K+1，\u5176\u4e2d\u00a0KK\u00a0\u662f\u4e00\u4e2a\u5927\u4e8e\u603b\u8fb9\u6570\u00a0MM\u00a0\u7684\u6570\u3002<\/p>\n
\u4e3a\u4ec0\u4e48\u8fd9\u6837\u505a？\u8bbe\u4e00\u4e2a\u5272\u5305\u542b\u00a0kk\u00a0\u6761\u8fb9，\u5176\u5bb9\u91cf\u4e3a：<\/p>\n
\u2211(wi\u00d7K+1)=K\u00d7\u2211wi+k<\/p>\n
\u7b2c\u4e00\u90e8\u5206\u00a0K\u00d7\u2211wi\u53cd\u6620\u7684\u662f\u7ecf\u6d4e\u635f\u5931（\u4e3b\u76ee\u6807）<\/p>\n<\/li>\n
\u7b2c\u4e8c\u90e8\u5206\u00a0k\u00a0\u53cd\u6620\u7684\u662f\u5272\u8fb9\u6570\u91cf（\u8f85\u76ee\u6807）<\/p>\n<\/li>\n<\/ul>\n
\u56e0\u4e3a\u00a0K>M\u2265k，\u6240\u4ee5\u4efb\u4f55\u4e24\u4e2a\u5272\u7684\u6bd4\u8f83，\u9996\u5148\u770b\u7684\u662f\u00a0\u2211wi\u00a0\u7684\u5927\u5c0f（\u4e3b\u76ee\u6807\u4f18\u5148）；\u53ea\u6709\u5f53\u00a0\u2211wi \u76f8\u7b49\u65f6，\u624d\u4f1a\u6bd4\u8f83\u00a0k\u00a0\u7684\u5927\u5c0f（\u8f85\u76ee\u6807）\u3002<\/p>\n
\u9898\u76ee\u4e2d\u00a0M\u22641000，\u6240\u4ee5\u00a0K\u00a0\u53d6\u00a01001\u00a0\u6216\u66f4\u5927\u7684\u6570\u5373\u53ef\u3002<\/p>\n
\u5982\u679c\u00a0K=1001，\u90a3\u4e48\u4efb\u4f55\u4e24\u4e2a\u6700\u5c0f\u5272\u65b9\u6848，\u53ea\u8981\u635f\u5931\u5dee\u00a0\u22651，\u7f16\u7801\u540e\u7684\u5bb9\u91cf\u5dee\u5c31\u81f3\u5c11\u662f\u00a01001，\u8fdc\u8d85\u8fb9\u6570\u5dee\u7684\u6700\u5927\u503c\u00a01000，\u4e3b\u76ee\u6807\u4e00\u5b9a\u4f18\u5148\u3002<\/p>\n<\/li>\n
\u8dd1\u5b8c\u6700\u5927\u6d41\u540e，ans \/ K\u00a0\u5c31\u662f\u6700\u5c0f\u635f\u5931\u00a0C，ans % K\u00a0\u5c31\u662f\u6700\u5c11\u8fb9\u6570\u00a0T\u3002<\/p>\n<\/li>\n<\/ul>\n
\u5982\u679c\u53ea\u4e58\u00a0K \u800c\u4e0d\u52a0\u00a01，\u90a3\u4e48\u6240\u6709\u5272\u7684\u7f16\u7801\u5bb9\u91cf\u90fd\u662f\u00a0K\u00a0\u7684\u500d\u6570，\u8fb9\u6570\u4fe1\u606f\u5c31\u4e22\u5931\u4e86\u3002+1\u00a0\u7684\u4f5c\u7528\u5c31\u662f\u628a\u8fb9\u6570\u7f16\u7801\u8fdb\u4f59\u6570\u90e8\u5206\u2014\u2014\u6bcf\u6761\u88ab\u5272\u7684\u8fb9\u8d21\u732e\u00a01，\u603b\u8fb9\u6570\u5c31\u662f\u4f59\u6570\u3002<\/p>\n
\u9898\u76ee\u6765\u6e90：\u6d1b\u8c37 P1344 [USACO4.4] \u8ffd\u67e5\u574f\u725b\u5976 Pollutant Control<\/p>\n
\u9898\u76ee\u63cf\u8ff0：
\n\u4f60\u7b2c\u4e00\u5929\u63a5\u624b\u4e09\u9e7f\u725b\u5976\u516c\u53f8\u5c31\u53d1\u751f\u4e86\u4e00\u4ef6\u5012\u9709\u7684\u4e8b\u60c5：\u516c\u53f8\u4e0d\u5c0f\u5fc3\u53d1\u9001\u4e86\u4e00\u6279\u6709\u4e09\u805a\u6c30\u80fa\u7684\u725b\u5976\u3002\u9001\u8d27\u7f51\u7531\u4e00\u4e9b\u4ed3\u5e93\u548c\u8fd0\u8f93\u5361\u8f66\u7ec4\u6210，\u6bcf\u8f86\u5361\u8f66\u90fd\u5728\u5404\u81ea\u56fa\u5b9a\u7684\u4e24\u4e2a\u4ed3\u5e93\u4e4b\u95f4\u5355\u5411\u8fd0\u8f93\u725b\u5976\u3002\u4f60\u7684\u4efb\u52a1\u662f，\u5728\u4fdd\u8bc1\u574f\u725b\u5976\u4e0d\u9001\u5230\u96f6\u552e\u5546（\u4ed3\u5e93\u00a0N）\u7684\u524d\u63d0\u4e0b，\u505c\u6b62\u67d0\u4e9b\u8fd0\u8f93\u5361\u8f66，\u4f7f\u635f\u5931\u6700\u5c0f\u3002<\/p>\n
\u8f93\u5165\u683c\u5f0f：<\/p>\n
\u7b2c\u4e00\u884c：\u4e24\u4e2a\u6574\u6570\u00a0N(2\u2264N\u226432)\u3001M(0\u2264M\u22641000)<\/p>\n<\/li>\n
\u7b2c\u00a022\u00a0\u5230\u00a0M+1 \u884c：\u6bcf\u884c\u4e09\u4e2a\u6574\u6570\u00a0Si,Ei,Ci，\u8868\u793a\u4ece\u00a0Si\u5230\u00a0Ei \u7684\u4e00\u6761\u6709\u5411\u8fb9，\u5bb9\u91cf（\u505c\u6b62\u635f\u5931）\u4e3a\u00a0Ci<\/p>\n<\/li>\n<\/ul>\n
\u8f93\u51fa\u683c\u5f0f：<\/p>\n
\u4e24\u4e2a\u6574\u6570\u00a0C\u00a0\u548c\u00a0T：C\u00a0\u8868\u793a\u6700\u5c0f\u7684\u635f\u5931，T\u8868\u793a\u5728\u635f\u5931\u6700\u5c0f\u7684\u524d\u63d0\u4e0b，\u6700\u5c11\u8981\u505c\u6b62\u7684\u5361\u8f66\u6570<\/p>\n<\/li>\n<\/ul>\n
\u8f93\u5165\u6837\u4f8b：<\/p>\n
4 5
\n1 3 100
\n3 2 50
\n2 4 60
\n1 2 40
\n2 3 80<\/p>\n
\u8f93\u51fa\u6837\u4f8b：<\/p>\n
60 1<\/p>\n
\u628a\u6bcf\u4e2a\u4ed3\u5e93\u770b\u4f5c\u8282\u70b9，\u6bcf\u8f86\u5361\u8f66\u770b\u4f5c\u4e00\u6761\u6709\u5411\u8fb9，\u8fb9\u7684\u5bb9\u91cf\u5c31\u662f\u505c\u6b62\u8fd9\u8f86\u5361\u8f66\u7684\u7ecf\u6d4e\u635f\u5931\u3002<\/p>\n
\u6e90\u70b9\u00a0s=1（\u53d1\u8d27\u5de5\u5382）<\/p>\n<\/li>\n
\u6c47\u70b9\u00a0t=N（\u96f6\u552e\u5546）<\/p>\n<\/li>\n<\/ul>\n
\u76ee\u6807\u662f\u8ba9\u00a01\u00a0\u548c\u00a0N\u00a0\u4e0d\u8fde\u901a，\u5373\u627e\u5230\u4e00\u4e2a\u5272\u3002\u6700\u5c0f\u5272\u7684\u5bb9\u91cf\u5c31\u662f\u6700\u5c0f\u7684\u7ecf\u6d4e\u635f\u5931\u3002<\/p>\n
#include <bits\/stdc++.h>
\nusing namespace std;
\ntypedef long long ll;<\/p>\n
const int MAXN = 35; \/\/ N <= 32
\nconst int MAXM = 1005; \/\/ M <= 1000
\nconst ll INF = 4e18;
\nconst ll K = 1001; \/\/ \u5927\u4e8e M \u7684\u5927\u6570<\/p>\n
struct Edge {
\n int to, rev;
\n ll cap;
\n};<\/p>\n
vector<Edge> g[MAXN];
\nint level[MAXN], iter[MAXN];
\nint n, m;<\/p>\n
\/\/ \u6dfb\u52a0\u4e00\u6761\u6709\u5411\u8fb9\u53ca\u5176\u53cd\u5411\u8fb9
\nvoid add_edge(int from, int to, ll cap) {
\n g[from].push_back({to, (int)g[to].size(), cap});
\n g[to].push_back({from, (int)g[from].size() – 1, 0});
\n}<\/p>\n
\/\/ BFS \u6784\u5efa\u5c42\u6b21\u56fe
\nbool bfs(int s, int t) {
\n memset(level, -1, sizeof(level));
\n queue<int> q;
\n level[s] = 0;
\n q.push(s);
\n while (!q.empty()) {
\n int v = q.front(); q.pop();
\n for (auto &e : g[v]) {
\n if (e.cap > 0 && level[e.to] < 0) {
\n level[e.to] = level[v] + 1;
\n q.push(e.to);
\n }
\n }
\n }
\n return level[t] >= 0;
\n}<\/p>\n
\/\/ DFS \u5bfb\u627e\u589e\u5e7f\u8def
\nll dfs(int v, int t, ll f) {
\n if (v == t) return f;
\n for (int &i = iter[v]; i < (int)g[v].size(); i++) {
\n Edge &e = g[v][i];
\n if (e.cap > 0 && level[v] < level[e.to]) {
\n ll d = dfs(e.to, t, min(f, e.cap));
\n if (d > 0) {
\n e.cap -= d;
\n g[e.to][e.rev].cap += d;
\n return d;
\n }
\n }
\n }
\n return 0;
\n}<\/p>\n
\/\/ Dinic \u6700\u5927\u6d41
\nll max_flow(int s, int t) {
\n ll flow = 0;
\n while (bfs(s, t)) {
\n memset(iter, 0, sizeof(iter));
\n ll f;
\n while ((f = dfs(s, t, INF)) > 0) {
\n flow += f;
\n }
\n }
\n return flow;
\n}<\/p>\n
int main() {
\n ios::sync_with_stdio(false);
\n cin.tie(0);<\/p>\n
cin >> n >> m;
\n for (int i = 0; i < m; i++) {
\n int u, v;
\n ll w;
\n cin >> u >> v >> w;
\n \/\/ \u6838\u5fc3\u6280\u5de7：\u8fb9\u6743\u7f16\u7801\u4e3a w * K + 1
\n add_edge(u, v, w * K + 1);
\n }<\/p>\n
ll ans = max_flow(1, n);
\n cout << ans \/ K << " " << ans % K << "\\\\n";
\n return 0;
\n}<\/p>\n
\u7b2c34-36\u884c：\u6dfb\u52a0\u8fb9\u65f6，\u5bb9\u91cf\u8bbe\u7f6e\u4e3a\u00a0w * K + 1\u3002\u8fd9\u5c31\u662f\u6838\u5fc3\u7684\u7f16\u7801\u6280\u5de7\u3002<\/p>\n
\u7b2c38-60\u884c：\u6807\u51c6Dinic\u7b97\u6cd5\u3002bfs\u00a0\u6784\u5efa\u5c42\u6b21\u56fe，dfs\u00a0\u5728\u5c42\u6b21\u56fe\u4e0a\u5bfb\u627e\u589e\u5e7f\u8def\u3002<\/p>\n
\u7b2c67-68\u884c：\u8dd1\u5b8c\u6700\u5927\u6d41\u540e：<\/p>\n
ans \/ K\u00a0\u5f97\u5230\u6700\u5c0f\u635f\u5931（\u4e3b\u76ee\u6807）<\/p>\n<\/li>\n
ans % K\u00a0\u5f97\u5230\u6700\u5c11\u8fb9\u6570（\u8f85\u76ee\u6807）<\/p>\n<\/li>\n<\/ul>\n
\u8f93\u5165\u6837\u4f8b\u4e2d，M=5M=5，K=1001K=1001\u3002<\/p>\n
\u5404\u8fb9\u7f16\u7801\u540e\u7684\u5bb9\u91cf：<\/p>\n
1->3：100\u00d71001+1=100101<\/p>\n<\/li>\n
3->2：50\u00d71001+1=50051<\/p>\n<\/li>\n
2->4：60\u00d71001+1=60061<\/p>\n<\/li>\n
1->2：40\u00d71001+1=40041<\/p>\n<\/li>\n
2->3：80\u00d71001+1=80081<\/p>\n<\/li>\n<\/ul>\n
\u8dd1\u6700\u5927\u6d41\u5f97\u5230\u00a0ans=60061（\u5272\u6389\u8fb9\u00a02->4，\u5bb9\u91cf60，\u8fb9\u65701）\u3002<\/p>\n
C=60061\/1001=60<\/p>\n<\/li>\n
T=60061%1001=1<\/p>\n<\/li>\n<\/ul>\n
\u8f93\u51fa\u00a060 1，\u4e0e\u6837\u4f8b\u4e00\u81f4\u3002<\/p>\n
\u65f6\u95f4\u590d\u6742\u5ea6：Dinic\u7b97\u6cd5\u5728\u4e00\u822c\u56fe\u4e0a\u7684\u590d\u6742\u5ea6\u4e3a\u00a0O(V^2E)\u3002\u672c\u9898\u00a0V\u226432，E\u22641000，\u5b8c\u5168\u53ef\u884c\u3002<\/p>\n<\/li>\n
\u7a7a\u95f4\u590d\u6742\u5ea6：O(V+E)\u3002<\/p>\n<\/li>\n<\/ul>\n
\u9664\u4e86\u7f16\u7801\u6280\u5de7，\u4e5f\u53ef\u4ee5\u5206\u4e24\u6b21\u5efa\u56fe：<\/p>\n
\u7b2c\u4e00\u904d：\u6309\u539f\u8fb9\u6743\u5efa\u56fe，\u8dd1\u6700\u5927\u6d41\u5f97\u5230\u6700\u5c0f\u635f\u5931\u00a0C\u3002<\/p>\n<\/li>\n
\u7b2c\u4e8c\u904d：\u5c06\u6240\u6709\u8fb9\u7684\u5bb9\u91cf\u6539\u4e3a1，\u8dd1\u6700\u5927\u6d41\u5f97\u5230\u6700\u5c11\u8fb9\u6570\u00a0T\u3002<\/p>\n<\/li>\n
\u8fd9\u79cd\u65b9\u6cd5\u66f4\u76f4\u89c2，\u4f46\u9700\u8981\u8dd1\u4e24\u904d，\u4ee3\u7801\u91cf\u7565\u5927\u3002\u7f16\u7801\u6280\u5de7\u5219\u4e00\u6b21\u5efa\u56fe\u3001\u4e00\u6b21\u8dd1\u6d41，\u66f4\u52a0\u7b80\u6d01\u9ad8\u6548\u3002<\/p>\n
\u7f51\u7edc\u6d41\u6700\u5c0f\u5272\u662f\u7b97\u6cd5\u7ade\u8d5b\u4e2d\u4e00\u4e2a\u6781\u5176\u91cd\u8981\u7684\u6a21\u578b\u3002\u4ece\u201c\u5207\u65ad\u8865\u7ed9\u7ebf\u201d\u5230\u201c\u8ffd\u67e5\u574f\u725b\u5976\u201d，\u5b83\u7684\u6838\u5fc3\u601d\u60f3\u59cb\u7ec8\u5982\u4e00：\u7528\u6700\u5c0f\u7684\u4ee3\u4ef7，\u5f7b\u5e95\u963b\u65ad\u6e90\u70b9\u5230\u6c47\u70b9\u7684\u6240\u6709\u901a\u8def\u3002\u800c\u6700\u5927\u6d41\u6700\u5c0f\u5272\u5b9a\u7406\u5219\u4e3a\u6211\u4eec\u63d0\u4f9b\u4e86\u4e00\u4e2a\u5f3a\u5927\u7684\u5de5\u5177\u2014\u2014\u6c42\u6700\u5c0f\u5272，\u5c31\u662f\u6c42\u6700\u5927\u6d41\u3002<\/p>\n
P1344\u8fd9\u9053\u9898\u7684\u7cbe\u9ad3\u5728\u4e8e\u591a\u76ee\u6807\u4f18\u5316\u7684\u5904\u7406\u6280\u5de7：\u5f53\u6211\u4eec\u9700\u8981\u5728\u201c\u4e3b\u76ee\u6807\u6700\u4f18\u201d\u7684\u524d\u63d0\u4e0b\u4f18\u5316\u201c\u8f85\u76ee\u6807\u201d\u65f6，\u53ef\u4ee5\u901a\u8fc7\u8fb9\u6743\u7f16\u7801\u7684\u65b9\u5f0f，\u628a\u4e24\u4e2a\u76ee\u6807\u5408\u5e76\u5230\u4e00\u6761\u8fb9\u7684\u5bb9\u91cf\u4e2d，\u4e00\u6b21\u6700\u5927\u6d41\u540c\u65f6\u89e3\u51b3\u4e24\u4e2a\u95ee\u9898\u3002<\/p>\n
\u4e09\u4e2a\u5173\u952e\u70b9：<\/p>\n
\u6838\u5fc3\u5b9a\u7406：\u6700\u5927\u6d41 = \u6700\u5c0f\u5272，\u6c42\u6700\u5c0f\u5272\u5c31\u662f\u6c42\u6700\u5927\u6d41\u3002<\/p>\n<\/li>\n
\u6838\u5fc3\u6280\u5de7：\u8fb9\u6743\u7f16\u7801\u4e3a\u00a0w\u00d7K+1（K>M），\u4e00\u6b21\u6700\u5927\u6d41\u540c\u65f6\u5f97\u5230\u6700\u5c0f\u5272\u503c\u548c\u6700\u5c11\u8fb9\u6570\u3002<\/p>\n<\/li>\n
\u6838\u5fc3\u6a21\u578b：\u51e1\u662f\u201c\u5207\u65ad\u6240\u6709\u901a\u8def\u7684\u6700\u5c0f\u4ee3\u4ef7\u201d\u7c7b\u95ee\u9898，\u90fd\u53ef\u4ee5\u5efa\u6a21\u4e3a\u6700\u5c0f\u5272\u3002<\/p>\n<\/li>\n
\u201c\u6700\u5c0f\u5272\u6559\u4f1a\u6211\u4eec：\u6709\u65f6\u5019，\u89e3\u51b3\u95ee\u9898\u7684\u6700\u4f73\u65b9\u5f0f\u4e0d\u662f\u627e\u5230\u6700\u5feb\u7684\u8def，\u800c\u662f\u627e\u5230\u6700\u4fbf\u5b9c\u7684\u2018\u65ad\u8def\u2019\u2014\u2014\u5207\u65ad，\u6709\u65f6\u6bd4\u8fde\u901a\u66f4\u9700\u8981\u667a\u6167\u3002\u201d<\/p>\n
\u300a\u7b97\u6cd5\u5bfc\u8bba\u300b\u00a0（Introduction to Algorithms）\u7b2c26\u7ae0\u2014\u2014\u6700\u5927\u6d41<\/p>\n<\/li>\n
OI-Wiki：\u7f51\u7edc\u6d41 – \u6700\u5c0f\u5272<\/p>\n<\/li>\n
\u6d1b\u8c37 P1344 [USACO4.4] \u8ffd\u67e5\u574f\u725b\u5976 Pollutant Control<\/p>\n<\/li>\n
\u300a\u6700\u5c0f\u5272\u6a21\u578b\u5728\u4fe1\u606f\u5b66\u7ade\u8d5b\u4e2d\u7684\u5e94\u7528\u300b\u00a0\u2014\u2014 \u80e1\u4f2f\u6d9b（\u56fd\u5bb6\u96c6\u8bad\u961f\u8bba\u6587）<\/p>\n<\/li>\n
HDU 6214 Smallest Minimum Cut\u00a0\u2014\u2014 \u540c\u7c7b\u7ec3\u4e60\u9898<\/p>\n<\/li>\n","protected":false},"excerpt":{"rendered":"
\u5982\u679c\u8bf4\u6700\u5927\u6d41\u662f\u201c\u5982\u4f55\u7528\u6700\u5feb\u7684\u901f\u5ea6\u628a\u6c34\u4eceA\u9001\u5230B\u201d，\u90a3\u4e48\u6700\u5c0f\u5272\u5c31\u662f\u201c\u5982\u4f55\u7528\u6700\u5c11\u7684\u4ee3\u4ef7\u5207\u65adA\u5230B\u7684\u6240\u6709\u901a\u8def\u201d\u2014\u2014\u5b83\u7528\u4e00\u5f20\u7f51\u7edc\u548c\u4e00\u628a\u201c\u526a\u5200\u201d，\u56de\u7b54\u4e86\u6240\u6709\u963b\u65ad\u95ee\u9898\u7684\u6700\u4f18\u89e3\u3002\u5f15\u8a00\u5047\u8bbe\u4f60\u662f\u4e00\u540d\u6307\u6325\u5b98，\u654c\u519b\u6709\u4e00\u6761\u4ece\u540e\u65b9\u57fa\u5730\u5230\u524d\u7ebf\u7684\u8865\u7ed9\u7ebf\u7f51\u7edc\u2014\u2014\u591a\u6761\u9053\u8def\u4ea4\u7ec7，\u56db\u901a\u516b\u8fbe\u3002\u4f60\u7684\u4efb\u52a1\u662f：\u70b8\u6389\u6700\u5c11\u7684\u9053\u8def（\u6216\u8005\u8bf4\u82b1\u8d39\u6700\u5c0f\u7684\u4ee3\u4ef7），\u8ba9\u8865\u7ed9\u5f7b\u5e95\u65e0\u6cd5\u9001\u8fbe\u524d\u7ebf\u3002\u6bcf\u6761\u9053\u8def\u7684\u70b8\u6bc1\u6210\u672c\u4e0d\u540c，<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[427],"topic":[],"class_list":["post-86985","post","type-post","status-publish","format-standard","hentry","category-server","tag-427"],"yoast_head":"\n