{"id":460,"date":"2013-07-31T15:55:43","date_gmt":"2013-07-31T07:55:43","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=460"},"modified":"2013-07-31T15:55:43","modified_gmt":"2013-07-31T07:55:43","slug":"km%e7%ae%97%e6%b3%95-%e8%af%a6%e8%a7%a3%e6%a8%a1%e6%9d%bf","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=460","title":{"rendered":"KM\u7b97\u6cd5 \u8be6\u89e3+\u6a21\u677f"},"content":{"rendered":"<p>\u672c\u6587\u8f6c\u8f7d\u81ea\uff1a<a href=\"http:\/\/blog.sina.com.cn\/s\/blog_691ce2b701016reh.html\">http:\/\/blog.sina.com.cn\/s\/blog_691ce2b701016reh.html<\/a><br \/>\n&nbsp;<br \/>\n\u5148\u8bf4KM\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u7684\u6700\u4f73\u5339\u914d\u601d\u60f3\uff0c\u518d\u8be6\u8bb2KM\u7684\u5b9e\u73b0\u3002<br \/>\n\u3010KM\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u7684\u6700\u4f73\u5339\u914d\u601d\u60f3\u3011<\/p>\n<div>\u5bf9\u4e8e\u5177\u6709\u4e8c\u90e8\u5212\u5206( V1, V2 )\u7684\u52a0\u6743\u5b8c\u5168\u4e8c\u5206\u56fe\uff0c\u5176\u4e2d V1= { x1, x2, x3, &#8230; , xn }\uff0c V2= { y1, y2, y3, &#8230; , yn }\uff0c\u8fb9&lt; xi, yj &gt;\u5177\u6709\u6743\u503c W<sub>i,j \u3002<\/sub>\u8be5\u5e26\u6743\u4e8c\u5206\u56fe\u4e2d\u4e00\u4e2a\u603b\u6743\u503c\u6700\u5927\u7684\u5b8c\u7f8e\u5339\u914d\uff0c\u79f0\u4e4b\u4e3a\u6700\u4f73\u5339\u914d\u3002<\/div>\n<div>\u00a0<wbr \/><wbr \/><\/div>\n<div>\u8bb0 L(x) \u8868\u793a\u7ed3\u70b9 x \u7684\u6807\u8bb0\u91cf\uff0c\u5982\u679c\u5bf9\u4e8e\u4e8c\u90e8\u56fe\u4e2d\u7684\u4efb\u4f55\u8fb9&lt;x,y&gt;\uff0c\u90fd\u6709 L(x)+ L(y)&gt;= W<sub>x,y<\/sub>\uff0c\u6211\u4eec\u79f0 L \u4e3a\u4e8c\u90e8\u56fe\u7684\u53ef\u884c\u9876\u6807\u3002<\/div>\n<div>\u8bbe G(V,E) \u4e3a\u4e8c\u90e8\u56fe\uff0c G'(V,E&#8217;) \u4e3a\u4e8c\u90e8\u56fe\u7684\u5b50\u56fe\u3002\u5982\u679c\u5bf9\u4e8e G&#8217; \u4e2d\u7684\u4efb\u4f55\u8fb9&lt;x,y&gt; \u6ee1\u8db3\uff0c L(x)+ L(y)== W<sub>x,y<\/sub>\uff0c\u6211\u4eec\u79f0 G'(V,E&#8217;) \u4e3a G(V,E) \u7684\u7b49\u4ef7\u5b50\u56fe\u3002<\/div>\n<div>\u00a0<wbr \/><wbr \/><\/div>\n<div>\u5b9a\u7406\u4e00\uff1a\u8bbe L \u662f\u4e8c\u90e8\u56fe G \u7684\u53ef\u884c\u9876\u6807\u3002\u82e5 L \u7b49\u4ef7\u5b50\u56fe G<sub>L\u00a0<wbr \/><wbr \/><\/sub>\u6709\u5b8c\u7f8e\u5339\u914d M\uff0c\u5219 M \u662f G \u7684\u6700\u4f73\u5339\u914d\u3002<\/div>\n<div>\u8bc1\u660e\uff1a\u7531\u4e8e G<sub>L<\/sub>\u00a0<wbr \/><wbr \/>\u662f G \u7684\u7b49\u4ef7\u5b50\u56fe\uff0cM \u662f G<sub>L<\/sub>\u00a0<wbr \/><wbr \/>\u7684\u5b8c\u7f8e\u5339\u914d\uff0c\u6240\u4ee5\uff0cM \u4e5f\u662f G\u00a0<wbr \/><wbr \/>\u00a0\u7684\u5b8c\u7f8e\u5339\u914d\u3002\u4ee5\u7531\u4e8e\u5bf9\u4e8e\u5339\u914d M \u7684\u6bcf\u6761\u8fb9 e \uff0c\u90fd\u6709 e\u2208 E( G<sub>L<\/sub>\u00a0<wbr \/><wbr \/>)\uff0c\u800c\u4e14 M \u4e2d\u6bcf\u6761\u8fb9\u8986\u76d6\u6bcf\u4e2a\u9876\u70b9\u6b63\u597d\u4e00\u6b21\uff0c\u6240\u4ee5<\/div>\n<div>W( M )=\u00a0<wbr \/><wbr \/>\u00e5\u00a0<wbr \/><wbr \/>W(e), e\u2208 M =\u00a0<wbr \/><wbr \/>\u00e5\u00a0<wbr \/><wbr \/>L(x), x\u2208 V<\/div>\n<div>\u53e6\u4e00\u65b9\u9762\uff0c\u5bf9\u4e8e G \u7684\u4efb\u4f55\u5b8c\u7f8e\u5339\u914d M&#8217; \u6709<\/div>\n<div>W( M&#8217; )=\u00a0<wbr \/><wbr \/>\u00e5\u00a0<wbr \/><wbr \/>W(e), e\u2208 M&#8217;\u00a0<wbr \/><wbr \/>&lt;=\u00a0<wbr \/><wbr \/>\u00e5\u00a0<wbr \/><wbr \/>L(x), x\u2208 V<\/div>\n<div>\u4e8e\u662f W( M )&gt;= W( M&#8217; )\uff0c\u5373 M \u662f G\u00a0<wbr \/><wbr \/>\u7684\u6700\u4f18\u5339\u914d\u3002<\/div>\n<div>\u00a0<wbr \/><wbr \/><\/div>\n<div>\u7531\u4e0a\u8ff0\u5b9a\u7406\uff0c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u6765\u4e0d\u65ad\u4fee\u6539\u53ef\u884c\u9876\u6807\uff0c\u5f97\u5230\u7b49\u4ef7\u5b50\u56fe\uff0c\u4ece\u800c\u6c42\u51fa\u6700\u4f73\u5339\u914d\u3002<\/div>\n<div>\u5c31\u50cf\u5308\u7259\u5229\u7b97\u6cd5\u4e00\u6837\uff0c\u6211\u4eec\u4f9d\u6b21\u4e3a\u6bcf\u4e00\u4e2a\u9876\u70b9 i \u5bfb\u627e\u589e\u5e7f\u8def\u5f84\uff0c\u5982\u679c\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u5931\u8d25\uff0c\u6211\u4eec\u5c31\u4fee\u6539\u76f8\u5e94\u7684\u53ef\u884c\u9876\u6807\uff0c\u6765\u5f97\u5230\u589e\u5e7f\u8def\u5f84\u3002<\/div>\n<div>\u5982\u56fe\uff1a<\/div>\n<div>|\u00a0<wbr \/><wbr \/>\u00a01\u00a0<wbr \/><wbr \/>\u00a02\u00a0<wbr \/><wbr \/>\u00a03\u00a0<wbr \/><wbr \/>\u00a0|<\/div>\n<div>|\u00a0<wbr \/><wbr \/>\u00a03\u00a0<wbr \/><wbr \/>\u00a02\u00a0<wbr \/><wbr \/>\u00a04\u00a0<wbr \/><wbr \/>\u00a0|<\/div>\n<div>|\u00a0<wbr \/><wbr \/>\u00a02\u00a0<wbr \/><wbr \/>\u00a03\u00a0<wbr \/><wbr \/>\u00a05\u00a0<wbr \/><wbr \/>\u00a0|<\/div>\n<div>\u82e5\u8981\u5bf9\u8fd9\u4e2a\u5b8c\u5168\u4e8c\u5206\u56fe\u6c42\u6700\u4f73\u5339\u914d<\/div>\n<div>\u00a0<wbr \/><wbr \/><\/div>\n<div>\u521d\u59cb\u5316\uff1a<\/div>\n<div>Lx(1)= max{ y| w(1,y), 1&lt;= y&lt;= 3 }= max{ 1, 2, 3 }= 3, Ly(1)= 0<\/div>\n<div>Lx(2)= max{ 3, 2, 4 }= 4, Ly(2)= 0<\/div>\n<div>Lx(3)= max{ 2, 3, 5 }= 5, Ly(3)= 0;<\/div>\n<div>\u6211\u4eec\u5efa\u7acb\u7b49\u4ef7\u5b50\u56fe( \u6ee1\u8db3 Lx(x)+ Ly(y)== W(x,y) ) \u5982\u4e0b\uff1a<\/div>\n<div><img decoding=\"async\" title=\"km\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u6700\u4f73\u5339\u914d\" alt=\"km\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u6700\u4f73\u5339\u914d\" src=\"http:\/\/blogimg.chinaunix.net\/blog\/upfile2\/100412145048.jpg\" border=\"0\" \/><\/div>\n<div>\u5bf9\u4e8e\u8be5\u56fe\uff0c\u8fd0\u7528\u5308\u7259\u5229\u7b97\u6cd5\u5bf9 X\u00a0<wbr \/><wbr \/>\u90e8\u9876\u70b9 1 \u6c42\u589e\u5e7f\u8def\u5f84\uff0c\u5f97\u5230\u4e00\u4e2a\u5339\u914d\uff0c\u5982\u56fe( \u7ea2\u8272\u4ee3\u8868\u5339\u914d\u8fb9 )\uff1a<img decoding=\"async\" title=\"km\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u6700\u4f73\u5339\u914d\" alt=\"km\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u6700\u4f73\u5339\u914d\" src=\"http:\/\/blogimg.chinaunix.net\/blog\/upfile2\/100412145027.jpg\" border=\"0\" \/><\/div>\n<div>\u00a0<wbr \/><wbr \/>\u5bf9 X \u90e8\u9876\u70b9 2 \u6c42\u589e\u5e7f\u8def\u5f84\u5931\u8d25\uff0c\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u7684\u8fc7\u7a0b\u4e3a X 2-&gt; Y 3-&gt; X 1\u3002\u6211\u4eec\u628a\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u5931\u8d25\u7684 DFS \u7684\u4ea4\u9519\u6811\u4e2d\uff0c\u5728 X \u90e8\u9876\u70b9\u96c6\u79f0\u4e4b\u4e3a S\uff0c \u5728 Y \u90e8\u7684\u9876\u70b9\u96c6\u79f0\u4e4b\u4e3a T\u3002\u5219 S= { 1, 2 }\uff0cT= { 3 }\u3002\u73b0\u5728\u6211\u4eec\u5c31\u901a\u8fc7\u4fee\u6539\u9876\u6807\u503c\u6765\u6269\u5927\u7b49\u4ef7\u5b50\u56fe\uff0c\u5982\u4f55\u4fee\u6539\u3002<\/div>\n<div>\u00a0<wbr \/><wbr \/><\/div>\n<div>1)\u00a0<wbr \/><wbr \/>\u00a0<wbr \/><wbr \/>\u00a0\u6211\u4eec\u5bfb\u627e\u4e00\u4e2a d \u503c\uff0c\u4f7f\u5f97 d= min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x\u2208 S, y\u2209\u00a0<wbr \/><wbr \/>T }\uff0c\u56e0\u4e9b\uff0c\u8fd9\u65f6 d= min{<\/div>\n<div>Lx(1)+Ly(1)-W(1,1),\u00a0<wbr \/><wbr \/>\u00a0Lx(1)+Ly(2)-W(1,2),\u00a0<wbr \/><wbr \/>\u00a0Lx(2)+Ly(1)-W(2,1),\u00a0<wbr \/><wbr \/>\u00a0Lx(2)+Ly(2)-W(2,2) }=<\/div>\n<div>min{ 3+0- 1, 3+0-2,\u00a0<wbr \/><wbr \/>\u00a04+0-3,\u00a0<wbr \/><wbr \/>\u00a04+0-2 }= min{ 2, 1, 1, 2 }= 1\u3002<\/div>\n<div>\u5bfb\u627e\u6700\u5c0f\u7684 d \u662f\u4e3a\u4e86\u4fdd\u8bc1\u4fee\u6539\u540e\u4ecd\u6ee1\u8db3\u6027\u8d28\u5bf9\u4e8e\u8fb9 &lt;x,y&gt; \u6709 Lx(x)+ Ly(y)&gt;= W(x,y)\u3002<\/div>\n<div>\u00a0<wbr \/><wbr \/><\/div>\n<div>2)\u00a0<wbr \/><wbr \/>\u00a0<wbr \/><wbr \/>\u00a0\u7136\u540e\u5bf9\u4e8e\u9876\u70b9 x<\/div>\n<div>1. \u5982\u679c x\u2208 S \u5219 Lx(x)= Lx(x)- d\u3002<\/div>\n<div>2. \u5982\u679c x\u2208 T\u00a0<wbr \/><wbr \/>\u5219 Ly(x)= Ly(x)+ d\u3002<\/div>\n<div>3. \u5176\u5b83\u60c5\u51b5\u4fdd\u6301\u4e0d\u53d8\u3002<\/div>\n<div>\u5982\u6b64\u4fee\u6539\u540e\uff0c\u6211\u4eec\u53d1\u73b0\u5bf9\u4e8e\u8fb9&lt;x,y&gt;\uff0c\u9876\u6807 Lx(x)+ Ly(y) \u7684\u503c\u4e3a<\/div>\n<div>1.\u00a0<wbr \/><wbr \/>\u00a0Lx(x)- d+ Ly(y)+ d\uff0c\u00a0<wbr \/><wbr \/>\u00a0x\u2208 S, y\u2208\u00a0<wbr \/><wbr \/>T\u3002<\/div>\n<div>2.\u00a0<wbr \/><wbr \/>\u00a0Lx(x)+ Ly(y)\uff0c\u00a0<wbr \/><wbr \/>\u00a0<wbr \/><wbr \/>x\u2209\u00a0<wbr \/><wbr \/>S,\u00a0<wbr \/><wbr \/>\u00a0y\u2209\u00a0<wbr \/><wbr \/>T\u3002<\/div>\n<div>3.\u00a0<wbr \/><wbr \/>\u00a0Lx(x)- d+ Ly(y)\uff0c x\u2208 S, y\u2209\u00a0<wbr \/><wbr \/>T\u3002<\/div>\n<div>4.\u00a0<wbr \/><wbr \/>\u00a0Lx(x)+ Ly(y)+ d\uff0c x\u2209\u00a0<wbr \/><wbr \/>S, \u00a0<wbr \/><wbr \/>y\u2208\u00a0<wbr \/><wbr \/>T\u3002<\/div>\n<div>\u6613\u77e5\uff0c\u4fee\u6539\u540e\u5bf9\u4e8e\u4efb\u4f55\u8fb9\u4ecd\u6ee1\u8db3 Lx(x)+ Ly(y)&gt;= W(x,y)\uff0c\u5e76\u4e14\u7b2c\u4e09\u79cd\u60c5\u51b5\u9876\u6807\u503c\u51cf\u5c11\u4e86 d\uff0c\u5982\u6b64\u5b9a\u4f1a\u4f7f\u7b49\u4ef7\u5b50\u56fe\u6269\u5927\u3002<\/div>\n<div>\u00a0<wbr \/><wbr \/><\/div>\n<div>\u5c31\u4e0a\u4f8b\u800c\u8a00: \u4fee\u6539\u540e Lx(1)= 2, Lx(2)= 3, Lx(3)= 5, Ly(1)= 0, Ly(1)= 0, Ly(2)= 0, Ly(3)= 1\u3002<\/div>\n<div>\u8fd9\u65f6 Lx(2)+Ly(1)=3+0=3= W(2,1)\uff0c\u5728\u7b49\u4ef7\u5b50\u56fe\u4e2d\u589e\u52a0\u4e86\u4e00\u6761\u8fb9\uff0c\u7b49\u4ef7\u5b50\u56fe\u53d8\u4e3a\uff1a<\/div>\n<div>\u00a0<wbr \/><wbr \/><img decoding=\"async\" title=\"km\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u6700\u4f73\u5339\u914d\" alt=\"km\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u6700\u4f73\u5339\u914d\" src=\"http:\/\/blogimg.chinaunix.net\/blog\/upfile2\/100412144857.jpg\" border=\"0\" \/><\/div>\n<div>\u5982\u6b64\u6309\u4ee5\u4e0a\u65b9\u6cd5\uff0c\u5f97\u5230\u7b49\u4ef7\u5b50\u56fe\u7684\u5b8c\u7f8e\u5339\u914d\u3002<\/div>\n<div>\u00a0<wbr \/><wbr \/><\/div>\n<div>\u53e6\u5916\u8ba1\u7b97 d \u503c\u7684\u65f6\u5019\u53ef\u4ee5\u8fdb\u884c\u4e00\u4e9b\u4f18\u5316\u3002<\/div>\n<div>\u5b9a\u4e49 slack(y)= min{ (x,y)| Lx(x)+ Ly(y)- W(x,y)\uff0cx\u2208 S, \u00a0<wbr \/><wbr \/>y\u2209\u00a0<wbr \/><wbr \/>T }<\/div>\n<div>\u8fd9\u6837\u80fd\u5728\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u7684\u65f6\u5019\u5c31\u987a\u4fbf\u5c06 slack \u6c42\u51fa\u3002<\/div>\n<p>\uff08\u4ee5\u4e0a\u4e3a\u6458\u4e0a\u7f51\u7edc\uff09<br \/>\n\u3010KM\u7b97\u6cd5\u53ca\u5176\u5177\u4f53\u8fc7\u7a0b\u3011<br \/>\n\uff081\uff09\u53ef\u884c\u70b9\u6807\uff1a\u6bcf\u4e2a\u70b9\u6709\u4e00\u4e2a\u6807\u53f7\uff0c\u8bb0lx[i]\u4e3aX\u65b9\u70b9i\u7684\u6807\u53f7\uff0cly[j]\u4e3aY\u65b9\u70b9j\u7684\u6807\u53f7\u3002\u5982\u679c\u5bf9\u4e8e\u56fe\u4e2d\u7684\u4efb\u610f\u8fb9(i, j, W)\u90fd\u6709lx[i]+ly[j]&gt;=W\uff0c\u5219\u8fd9\u4e00\u7ec4\u70b9\u6807\u662f<strong>\u53ef\u884c<\/strong>\u7684\u3002\u7279\u522b\u5730\uff0c\u5bf9\u4e8elx[i]+ly[j]=W\u7684\u8fb9(i, j, W)\uff0c\u79f0\u4e3a<strong>\u53ef\u884c\u8fb9<\/strong>\uff1b<br \/>\n\uff082\uff09KM \u7b97\u6cd5\u7684\u6838\u5fc3\u601d\u60f3\u5c31\u662f\u901a\u8fc7\u4fee\u6539\u67d0\u4e9b\u70b9\u7684\u6807\u53f7\uff08\u4f46\u8981\u6ee1\u8db3\u70b9\u6807\u59cb\u7ec8\u662f\u53ef\u884c\u7684\uff09\uff0c\u4e0d\u65ad\u589e\u52a0\u56fe\u4e2d\u7684\u53ef\u884c\u8fb9\u603b\u6570\uff0c\u76f4\u5230\u56fe\u4e2d\u5b58\u5728\u4ec5\u7531\u53ef\u884c\u8fb9\u7ec4\u6210\u7684\u5b8c\u5168\u5339\u914d\u4e3a\u6b62\uff0c\u6b64\u65f6\u8fd9\u4e2a \u5339\u914d\u4e00\u5b9a\u662f\u6700\u4f73\u7684\uff08\u56e0\u4e3a\u7531\u53ef\u884c\u70b9\u6807\u7684\u7684\u5b9a\u4e49\uff0c\u56fe\u4e2d\u7684\u4efb\u610f\u4e00\u4e2a\u5b8c\u5168\u5339\u914d\uff0c\u5176\u8fb9\u6743\u603b\u548c\u5747\u4e0d\u5927\u4e8e\u6240\u6709\u70b9\u7684\u6807\u53f7\u4e4b\u548c\uff0c\u800c\u4ec5\u7531\u53ef\u884c\u8fb9\u7ec4\u6210\u7684\u5b8c\u5168\u5339\u914d\u7684\u8fb9\u6743\u603b\u548c\u7b49\u4e8e\u6240 \u6709\u70b9\u7684\u6807\u53f7\u4e4b\u548c\uff0c\u6545\u8fd9\u4e2a\u5339\u914d\u662f\u6700\u4f73\u7684\uff09\u3002\u4e00\u5f00\u59cb\uff0c\u6c42\u51fa\u6bcf\u4e2a\u70b9\u7684\u521d\u59cb\u6807\u53f7\uff1alx[i]=max{e.W|e.x=i}\uff08\u5373\u6bcf\u4e2aX\u65b9\u70b9\u7684\u521d\u59cb\u6807\u53f7\u4e3a\u4e0e\u8fd9\u4e2aX\u65b9 \u70b9\u76f8\u5173\u8054\u7684\u6743\u503c\u6700\u5927\u7684\u8fb9\u7684\u6743\u503c\uff09\uff0cly[j]=0\uff08\u5373\u6bcf\u4e2aY\u65b9\u70b9\u7684\u521d\u59cb\u6807\u53f7\u4e3a0\uff09\u3002\u8fd9\u4e2a\u521d\u59cb\u70b9\u6807\u663e\u7136\u662f\u53ef\u884c\u7684\uff0c\u5e76\u4e14\uff0c<strong>\u4e0e\u4efb\u610f\u4e00\u4e2aX\u65b9\u70b9\u5173\u8054\u7684\u8fb9\u4e2d\u81f3\u5c11\u6709\u4e00\u6761\u53ef\u884c\u8fb9<\/strong>\uff1b<br \/>\n\uff083\uff09\u7136\u540e\uff0c\u4ece\u6bcf\u4e2aX\u65b9\u70b9\u5f00\u59cbDFS\u589e\u5e7f\u3002DFS\u589e\u5e7f\u7684\u8fc7\u7a0b\u4e0e\u6700\u5927\u5339\u914d\u7684Hungary\u7b97\u6cd5\u57fa\u672c\u76f8\u540c\uff0c\u53ea\u662f\u8981\u6ce8\u610f\u4e24\u70b9\uff1a\u4e00\u662f\u53ea\u627e\u53ef\u884c\u8fb9\uff0c\u4e8c\u662f\u8981\u628a\u641c\u7d22\u8fc7\u7a0b\u4e2d\u904d\u5386\u5230\u7684X\u65b9\u70b9\u5168\u90e8\u8bb0\u4e0b\u6765\uff08\u53ef\u4ee5\u7528vst\u641e\u4e00\u4e0b\uff09\uff0c\u4ee5\u8fdb\u884c\u540e\u9762\u7684\u4fee\u6539\uff1b<br \/>\n\uff084\uff09 \u589e\u5e7f\u7684\u7ed3\u679c\u6709\u4e24\u79cd\uff1a\u82e5\u6210\u529f\uff08\u627e\u5230\u4e86\u589e\u5e7f\u8f68\uff09\uff0c\u5219\u8be5\u70b9\u589e\u5e7f\u5b8c\u6210\uff0c\u8fdb\u5165\u4e0b\u4e00\u4e2a\u70b9\u7684\u589e\u5e7f\u3002\u82e5\u5931\u8d25\uff08\u6ca1\u6709\u627e\u5230\u589e\u5e7f\u8f68\uff09\uff0c\u5219\u9700\u8981\u6539\u53d8\u4e00\u4e9b\u70b9\u7684\u6807\u53f7\uff0c\u4f7f\u5f97\u56fe\u4e2d\u53ef\u884c\u8fb9\u7684 \u6570\u91cf\u589e\u52a0\u3002\u65b9\u6cd5\u4e3a\uff1a\u5c06\u6240\u6709\u5728\u589e\u5e7f\u8f68\u4e2d\uff08\u5c31\u662f\u5728\u589e\u5e7f\u8fc7\u7a0b\u4e2d\u904d\u5386\u5230\uff09\u7684X\u65b9\u70b9\u7684\u6807\u53f7\u5168\u90e8\u51cf\u53bb\u4e00\u4e2a\u5e38\u6570d\uff0c\u6240\u6709\u5728\u589e\u5e7f\u8f68\u4e2d\u7684Y\u65b9\u70b9\u7684\u6807\u53f7\u5168\u90e8\u52a0\u4e0a\u4e00\u4e2a\u5e38\u6570d\uff0c\u5219 \u5bf9\u4e8e\u56fe\u4e2d\u7684\u4efb\u610f\u4e00\u6761\u8fb9(i, j, W)\uff08i\u4e3aX\u65b9\u70b9\uff0cj\u4e3aY\u65b9\u70b9\uff09\uff1a<br \/>\n&lt;1&gt;i\u548cj\u90fd\u5728\u589e\u5e7f\u8f68\u4e2d\uff1a\u6b64\u65f6\u8fb9(i, j)\u7684(lx[i]+ly[j])\u503c\u4e0d\u53d8\uff0c\u4e5f\u5c31\u662f\u8fd9\u6761\u8fb9\u7684\u53ef\u884c\u6027\u4e0d\u53d8\uff08\u539f\u6765\u662f\u53ef\u884c\u8fb9\u5219\u73b0\u5728\u4ecd\u662f\uff0c\u539f\u6765\u4e0d\u662f\u5219\u73b0\u5728\u4ecd\u4e0d\u662f\uff09\uff1b<br \/>\n&lt;2&gt;i\u5728\u589e\u5e7f\u8f68\u4e2d\u800cj\u4e0d\u5728\uff1a\u6b64\u65f6\u8fb9(i, j)\u7684(lx[i]+ly[j])\u7684\u503c\u51cf\u5c11\u4e86d\uff0c\u4e5f\u5c31\u662f\u539f\u6765\u8fd9\u6761\u8fb9\u4e0d\u662f\u53ef\u884c\u8fb9\uff08\u5426\u5219j\u5c31\u4f1a\u88ab\u904d\u5386\u5230\u4e86\uff09\uff0c\u800c\u73b0\u5728\u53ef\u80fd\u662f\uff1b<br \/>\n&lt;3&gt;j\u5728\u589e\u5e7f\u8f68\u4e2d\u800ci\u4e0d\u5728\uff1a\u6b64\u65f6\u8fb9(i, j)\u7684(lx[i]+ly[j])\u7684\u503c\u589e\u52a0\u4e86d\uff0c\u4e5f\u5c31\u662f\u539f\u6765\u8fd9\u6761\u8fb9\u4e0d\u662f\u53ef\u884c\u8fb9\uff08\u82e5\u8fd9\u6761\u8fb9\u662f\u53ef\u884c\u8fb9\uff0c\u5219\u5728\u904d\u5386\u5230j\u65f6\u4f1a\u7d27\u63a5\u7740\u6267\u884cDFS(i)\uff0c\u6b64\u65f6i\u5c31\u4f1a\u88ab\u904d\u5386\u5230\uff09\uff0c\u73b0\u5728\u4ecd\u4e0d\u662f\uff1b<br \/>\n&lt;4&gt;i\u548cj\u90fd\u4e0d\u5728\u589e\u5e7f\u8f68\u4e2d\uff1a\u6b64\u65f6\u8fb9(i, j)\u7684(lx[i]+ly[j])\u503c\u4e0d\u53d8\uff0c\u4e5f\u5c31\u662f\u8fd9\u6761\u8fb9\u7684\u53ef\u884c\u6027\u4e0d\u53d8\u3002<br \/>\n\u8fd9 \u6837\uff0c\u5728\u8fdb\u884c\u4e86\u8fd9\u4e00\u6b65\u4fee\u6539\u64cd\u4f5c\u540e\uff0c\u56fe\u4e2d\u539f\u6765\u7684\u53ef\u884c\u8fb9\u4ecd\u53ef\u884c\uff0c\u800c\u539f\u6765\u4e0d\u53ef\u884c\u7684\u8fb9\u73b0\u5728\u5219\u53ef\u80fd\u53d8\u4e3a\u53ef\u884c\u8fb9\u3002\u90a3\u4e48d\u7684\u503c\u5e94\u53d6\u591a\u5c11\uff1f\u663e\u7136\uff0c\u6574\u4e2a\u70b9\u6807\u4e0d\u80fd\u5931\u53bb\u53ef\u884c\u6027\uff0c\u4e5f \u5c31\u662f\u5bf9\u4e8e\u4e0a\u8ff0\u7684\u7b2c&lt;2&gt;\u7c7b\u8fb9\uff0c\u5176lx[i]+ly[j]&gt;=W\u8fd9\u4e00\u6027\u8d28\u4e0d\u80fd\u88ab\u6539\u53d8\uff0c\u6545\u53d6\u6240\u6709\u7b2c&lt;2&gt;\u7c7b\u8fb9\u7684 (lx[i]+ly[j]-W)\u7684\u6700\u5c0f\u503c\u4f5c\u4e3ad\u503c\u5373\u53ef\u3002\u8fd9\u6837\u4e00\u65b9\u9762\u53ef\u4ee5\u4fdd\u8bc1\u70b9\u6807\u7684\u53ef\u884c\u6027\uff0c\u53e6\u4e00\u65b9\u9762\uff0c<strong>\u7ecf\u8fc7\u8fd9\u4e00\u6b65\u540e\uff0c\u56fe\u4e2d\u81f3\u5c11\u4f1a\u589e\u52a0\u4e00\u6761\u53ef\u884c\u8fb9\u3002<\/strong><br \/>\n\uff085\uff09\u4fee\u6539\u540e\uff0c\u7ee7\u7eed\u5bf9\u8fd9\u4e2aX\u65b9\u70b9DFS\u589e\u5e7f\uff0c\u82e5\u8fd8\u5931\u8d25\u5219\u7ee7\u7eed\u4fee\u6539\uff0c\u76f4\u5230\u6210\u529f\u4e3a\u6b62\uff1b<br \/>\n\uff086\uff09\u4ee5\u4e0a\u5c31\u662fKM\u7b97\u6cd5\u7684\u57fa\u672c\u601d\u8def\u3002\u4f46\u662f\u6734\u7d20\u7684\u5b9e\u73b0\u65b9\u6cd5\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n4)\u2014\u2014\u9700\u8981\u627eO(n)\u6b21\u589e\u5e7f\u8def\uff0c\u6bcf\u6b21\u589e\u5e7f\u6700\u591a\u9700\u8981\u4fee\u6539O(n)\u6b21\u9876\u6807\uff0c\u6bcf\u6b21\u4fee\u6539\u9876 \u6807\u65f6\u7531\u4e8e\u8981\u679a\u4e3e\u8fb9\u6765\u6c42d\u503c\uff0c\u590d\u6742\u5ea6\u4e3aO(n2)\u3002\u5b9e\u9645\u4e0aKM\u7b97\u6cd5\u7684\u590d\u6742\u5ea6\u662f\u53ef\u4ee5\u505a\u5230O(n3)\u7684\u3002\u6211\u4eec\u7ed9\u6bcf\u4e2aY\u9876\u70b9\u4e00\u4e2a\u201c\u677e\u5f1b\u91cf\u201d\u51fd\u6570slack\uff0c\u6bcf\u6b21\u5f00 \u59cb\u627e\u589e\u5e7f\u8def\u65f6\u521d\u59cb\u5316\u4e3a\u65e0\u7a77\u5927\u3002\u5728\u5bfb\u627e\u589e\u5e7f\u8def\u7684\u8fc7\u7a0b\u4e2d\uff0c\u68c0\u67e5\u8fb9(i,j)\u65f6\uff0c\u5982\u679c\u5b83\u4e0d\u5728\u76f8\u7b49\u5b50\u56fe\u4e2d\uff0c\u5219\u8ba9slack[j]\u53d8\u6210\u539f\u503c\u4e0e A[i]+B[j]-w[i,j]\u7684\u8f83\u5c0f\u503c\u3002\u8fd9\u6837\uff0c\u5728\u4fee\u6539\u9876\u6807\u65f6\uff0c\u53d6\u6240\u6709\u4e0d\u5728\u4ea4\u9519\u6811\u4e2d\u7684Y\u9876\u70b9\u7684slack\u503c\u4e2d\u7684\u6700\u5c0f\u503c\u4f5c\u4e3ad\u503c\u5373\u53ef\u3002\u4f46\u8fd8\u8981\u6ce8\u610f\u4e00\u70b9\uff1a\u4fee \u6539\u9876\u6807\u540e\uff0c\u8981\u628a\u6240\u6709\u4e0d\u5728\u4ea4\u9519\u6811\u4e2d\u7684Y\u9876\u70b9\u7684slack\u503c\u90fd\u51cf\u53bbd\u3002<br \/>\n\u3010\u6c42\u4e8c\u5206\u56fe\u7684\u6700\u5c0f\u5339\u914d\u3011<br \/>\n\u53ea\u9700\u628a\u6743\u503c\u53d6\u53cd\uff0c\u53d8\u4e3a\u8d1f\u7684\uff0c\u518d\u7528KM\u7b97\u51fa\u6700\u5927\u6743\u5339\u914d\uff0c\u53d6\u53cd\u5219\u4e3a\u5176\u6700\u5c0f\u6743\u5339\u914d\u3002<\/p>\n<pre>\nhdoj 2255\n#include <stdio.h>\n#include <string.h>\n#define M 310\n#define inf 0x3f3f3f3f\nint n,nx,ny;\nint link[M],lx[M],ly[M],slack[M];    \/\/lx,ly\u4e3a\u9876\u6807\uff0cnx,ny\u5206\u522b\u4e3ax\u70b9\u96c6y\u70b9\u96c6\u7684\u4e2a\u6570\nint visx[M],visy[M],w[M][M];\nint DFS(int x)\n{\n    visx[x] = 1;\n    for (int y = 1;y <= ny;y ++)\n    {\n        if (visy[y])\n            continue;\n        int t = lx[x] + ly[y] - w[x][y];\n        if (t == 0)       \/\/\n        {\n            visy[y] = 1;\n            if (link[y] == -1||DFS(link[y]))\n            {\n                link[y] = x;\n                return 1;\n            }\n        }\n        else if (slack[y] > t)  \/\/\u4e0d\u5728\u76f8\u7b49\u5b50\u56fe\u4e2dslack \u53d6\u6700\u5c0f\u7684\n            slack[y] = t;\n    }\n    return 0;\n}\nint KM()\n{\n    int i,j;\n    memset (link,-1,sizeof(link));\n    memset (ly,0,sizeof(ly));\n    for (i = 1;i <= nx;i ++)            \/\/lx\u521d\u59cb\u5316\u4e3a\u4e0e\u5b83\u5173\u8054\u8fb9\u4e2d\u6700\u5927\u7684\n        for (j = 1,lx[i] = -inf;j <= ny;j ++)\n            if (w[i][j] > lx[i])\n                lx[i] = w[i][j];\n    for (int x = 1;x <= nx;x ++)\n    {\n        for (i = 1;i <= ny;i ++)\n            slack[i] = inf;\n        while (1)\n        {\n            memset (visx,0,sizeof(visx));\n            memset (visy,0,sizeof(visy));\n            if (DFS(x))     \/\/\u82e5\u6210\u529f\uff08\u627e\u5230\u4e86\u589e\u5e7f\u8f68\uff09\uff0c\u5219\u8be5\u70b9\u589e\u5e7f\u5b8c\u6210\uff0c\u8fdb\u5165\u4e0b\u4e00\u4e2a\u70b9\u7684\u589e\u5e7f\n                break;  \/\/\u82e5\u5931\u8d25\uff08\u6ca1\u6709\u627e\u5230\u589e\u5e7f\u8f68\uff09\uff0c\u5219\u9700\u8981\u6539\u53d8\u4e00\u4e9b\u70b9\u7684\u6807\u53f7\uff0c\u4f7f\u5f97\u56fe\u4e2d\u53ef\u884c\u8fb9\u7684\u6570\u91cf\u589e\u52a0\u3002\n                        \/\/\u65b9\u6cd5\u4e3a\uff1a\u5c06\u6240\u6709\u5728\u589e\u5e7f\u8f68\u4e2d\uff08\u5c31\u662f\u5728\u589e\u5e7f\u8fc7\u7a0b\u4e2d\u904d\u5386\u5230\uff09\u7684X\u65b9\u70b9\u7684\u6807\u53f7\u5168\u90e8\u51cf\u53bb\u4e00\u4e2a\u5e38\u6570d\uff0c\n                        \/\/\u6240\u6709\u5728\u589e\u5e7f\u8f68\u4e2d\u7684Y\u65b9\u70b9\u7684\u6807\u53f7\u5168\u90e8\u52a0\u4e0a\u4e00\u4e2a\u5e38\u6570d\n            int d = inf;\n            for (i = 1;i <= ny;i ++)\n                if (!visy[i]&#038;&#038;d > slack[i])\n                    d = slack[i];\n            for (i = 1;i <= nx;i ++)\n                if (visx[i])\n                    lx[i] -= d;\n            for (i = 1;i <= ny;i ++)  \/\/\u4fee\u6539\u9876\u6807\u540e\uff0c\u8981\u628a\u6240\u6709\u4e0d\u5728\u4ea4\u9519\u6811\u4e2d\u7684Y\u9876\u70b9\u7684slack\u503c\u90fd\u51cf\u53bbd\n                if (visy[i])\n                    ly[i] += d;\n                else\n                    slack[i] -= d;\n        }\n    }\n    int res = 0;\n    for (i = 1;i <= ny;i ++)\n        if (link[i] > -1)\n            res += w[link[i]][i];\n    return res;\n}\nint main ()\n{\n    int i,j;\n    while (scanf (\"%d\",&n)!=EOF)\n    {\n        nx = ny = n;\n      \/\/  memset (w,0,sizeof(w));\n        for (i = 1;i <= n;i ++)\n            for (j = 1;j <= n;j ++)\n                scanf (\"%d\",&#038;w[i][j]);\n        int ans = KM();\n        printf (\"%dn\",ans);\n    }\n    return 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u672c\u6587\u8f6c\u8f7d\u81ea\uff1ahttp:\/\/blog.sina.com.cn\/s\/blog_691ce2b701016reh.html &nbsp; \u5148\u8bf4KM\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u7684\u6700\u4f73\u5339\u914d\u601d\u60f3\uff0c\u518d\u8be6\u8bb2KM\u7684\u5b9e\u73b0\u3002 \u3010KM\u7b97\u6cd5\u6c42\u4e8c\u5206\u56fe\u7684\u6700\u4f73\u5339\u914d\u601d\u60f3\u3011 \u5bf9\u4e8e\u5177\u6709\u4e8c\u90e8\u5212\u5206( V1, V2 )\u7684\u52a0\u6743\u5b8c\u5168\u4e8c\u5206\u56fe\uff0c\u5176\u4e2d V1= { x1, x2, x3, &#8230; , xn }\uff0c V2= { y1, y2, y3, &#8230; , yn }\uff0c\u8fb9&lt; xi, yj &gt;\u5177\u6709\u6743\u503c Wi,j \u3002\u8be5\u5e26\u6743\u4e8c\u5206\u56fe\u4e2d\u4e00\u4e2a\u603b\u6743\u503c\u6700\u5927\u7684\u5b8c\u7f8e\u5339\u914d\uff0c\u79f0\u4e4b\u4e3a\u6700\u4f73\u5339\u914d\u3002 \u00a0 \u8bb0 L(x) \u8868\u793a\u7ed3\u70b9 x \u7684\u6807\u8bb0\u91cf\uff0c\u5982\u679c\u5bf9\u4e8e\u4e8c\u90e8\u56fe\u4e2d\u7684\u4efb\u4f55\u8fb9&lt;x,y&gt;\uff0c\u90fd\u6709 L(x)+ L(y)&gt;= Wx,y\uff0c\u6211\u4eec\u79f0 L \u4e3a\u4e8c\u90e8\u56fe\u7684\u53ef\u884c\u9876\u6807\u3002 \u8bbe G(V,E) \u4e3a\u4e8c\u90e8\u56fe\uff0c G'(V,E&#8217;) \u4e3a\u4e8c\u90e8\u56fe\u7684\u5b50\u56fe\u3002\u5982\u679c\u5bf9\u4e8e G&#8217; \u4e2d\u7684\u4efb\u4f55\u8fb9&lt;x,y&gt; \u6ee1\u8db3\uff0c L(x)+ L(y)== Wx,y\uff0c\u6211\u4eec\u79f0 G'(V,E&#8217;) \u4e3a [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[185],"class_list":["post-460","post","type-post","status-publish","format-standard","hentry","category-study","tag-185"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/460","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=460"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/460\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=460"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=460"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=460"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}