{"id":631,"date":"2005-08-30T10:08:17","date_gmt":"2005-08-30T02:08:17","guid":{"rendered":"http:\/\/pony.hk\/?p=631"},"modified":"2020-09-29T11:15:29","modified_gmt":"2020-09-29T03:15:29","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e6%8b%93%e6%89%91%e6%8e%92%e5%ba%8f%e5%85%b3%e9%94%ae%e8%b7%af%e5%be%84%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/lnmp.ivan.xin\/?p=631","title":{"rendered":"\u6570\u636e\u7ed3\u6784----*\u62d3\u6251\u6392\u5e8f&&\u5173\u952e\u8def\u5f84\u7b97\u6cd5"},"content":{"rendered":"

#include<iostream.h>
\n#include<cstdlib>
\n#define outmax 3\/\/\u6700\u5927\u51fa\u5ea6
\n#define inmax 2\/\/\u6700\u5927\u5165\u5ea6
\n#define vex 9\/\/\u9876\u70b9\u4e2a\u6570
\n#define max 10000\/\/\u5b9a\u4e49\u6781\u5927\u503c
\nint linjie_0[vex][outmax]={{1,2,3},{4},{4},{5},{6,7},{7},{8},{8},{-1}};\/\/\u51fa\u90bb\u63a5\u9876\u70b9
\nint linjie_1[vex][inmax]={{-1},{0},{0},{0},{1,2},{3},{4},{4,5},{6,7}};\/\/\u5165\u90bb\u63a5\u9876\u70b9
\nint label_1[vex][3]={{0,0,3},{0,1,1},{0,1,1},{0,1,1},{0,2,2},{0,1,1},{0,1,1},{0,2,1},{0,2,0}};\/\/\u7b2c0\u5217\u662f\u62d3\u6251\u5217\u6807\u5fd7\u4f4d\uff0c\u7b2c1\u5217\u662f\u5165\u5ea6\uff0c\u7b2c2\u5217\u662f\u51fa\u5ea6
\nint labevl[vex][3]={{0,0,3},{0,1,1},{0,1,1},{0,1,1},{0,2,2},{0,1,1},{0,1,1},{0,2,1},{0,2,0}};\/\/\u7b2c0\u5217\u662f\u62d3\u6251\u5217\u6807\u5fd7\u4f4d\uff0c\u7b2c1\u5217\u662f\u5165\u5ea6\uff08\u5728\u62d3\u6251\u6392\u5e8f\u5b50\u7a0b\u5e8f\u4e2d\u503c\u8981\u6539\u53d8\uff09\uff0c\u7b2c2\u5217\u662f\u51fa\u5ea6
\nint juzhen[vex][vex];\/\/\u90bb\u63a5\u77e9\u9635
\nint tuopu[vex],tuopu_k=0;\/\/\u62d3\u6251\u5e8f\u5217
\nint ve[vex],vl[vex];\/\/\u9876\u70b9\uff0c\u4e8b\u4ef6\u7684\u6700\u65e9\u53d1\u751f\u65f6\u95f4\u548c\u6700\u8fdf\u53d1\u751f\u65f6\u95f4
\nint e[vex][vex],l[vex][vex];\/\/\u8fb9\uff0c\u6d3b\u52a8\u7684\u6700\u65e9\u5f00\u59cb\u65f6\u95f4\u548c\u6700\u8fdf\u5f00\u59cb\u65f6\u95f4\uff0c\u4e24\u8005\u76f8\u7b49\u7684\u5373\u4e3a\u5173\u952e\u8def\u5f84
\nvoid tuopupaixu();\/\/\u62d3\u6251\u6392\u5e8f\u5b50\u7a0b\u5e8f
\nvoid make_ve();\/\/\u4e8b\u4ef6\u6700\u65e9\u53d1\u751f\u65f6\u95f4\u5b50\u7a0b\u5e8f
\nvoid make_vl();\/\/\u4e8b\u4ef6\u6700\u8fdf\u53d1\u751f\u65f6\u95f4\u5b50\u7a0b\u5e8f
\nvoid critical_path();\/\/\u5173\u952e\u8def\u5f84\u5b50\u7a0b\u5e8f
\nint main()
\n{
\nint i,j;
\nfor(i=0;i<vex;i++)
\nfor(j=0;j<vex;j++)
\n{
\ntuopu=0;
\nve=0;
\njuzhen[j]=max;
\nvl=max;
\n}
\njuzhen[0][1]=6;
\njuzhen[0][2]=4;
\njuzhen[0][3]=5;
\njuzhen[1][4]=1;
\njuzhen[2][4]=1;
\njuzhen[3][5]=2;
\njuzhen[4][6]=9;
\njuzhen[4][7]=7;
\njuzhen[5][7]=4;
\njuzhen[6][8]=2;
\njuzhen[7][8]=4;\/\/\u521d\u59cb\u5316
\ntuopupaixu();
\nmake_ve();
\nmake_vl();
\ncritical_path();
\ncout<<endl;
\nsystem(\"pause\");
\nreturn 0;
\n}<\/p>\n

void tuopupaixu()
\n{
\nint i,j;
\nwhile(1)
\n{
\nfor(i=0;i<vex;i++)
\nif(labevl[0]==0)
\nj=1;
\nif(j==0)
\nbreak;
\nfor(i=0;i<vex;i++)
\nif(labevl[0]==0 && labevl[1]==0)
\n{
\nlabevl[0]=1;\/\/\u5220\u9664\u5df2\u7ecf\u6392\u5165\u62d3\u6251\u5e8f\u5217\u7684\u9876\u70b9
\ntuopu[tuopu_k]=i;\/\/\u62d3\u6251\u7f16\u53f7
\ntuopu_k++;
\nfor(j=0;j<labevl[2];j++)
\nlabevl[linjie_0[j]][1]--;\/\/\u4f7f\u548c\u6392\u5165\u62d3\u6251\u5e8f\u5217\u7684\u9876\u70b9\u76f8\u90bb\u7684\u9876\u70b9\u7684\u5165\u5ea6\u51cf1
\n}
\n}
\ncout<<\"\u62d3\u6251\u5e8f\u5217\uff1a\";
\nfor(i=0;i<vex;i++)
\ncout<<tuopu<<\" \";
\n}
\nvoid make_ve()
\n{
\ncout<<endl<<\"\u4e8b\u4ef6\u7684\u6700\u65e9\u5f00\u59cb\u65f6\u95f4\uff1a\";
\nint i,j;
\nint a1,a2,a3;
\nfor(i=0;i<vex;i++)\/\/\u6309\u62d3\u6251\u5e8f\u5217\u7684\u987a\u5e8f\u505a
\n{
\na1=tuopu;
\nfor(j=0;j<label_1[a1][2];j++)\/\/\u4ece\u6e90\u70b9\u5230\u6c47\u70b9\u63a8\u8fdb
\n{
\na2=linjie_0[a1][j];\/\/\u5411\u540e\u90bb\u63a5\u9876\u70b9
\na3=juzhen[a1][a2];\/\/\u8fb9\u7684\u6743\u503c
\nif(ve[a2]<ve[a1]+a3)
\nve[a2]=ve[a1]+a3;\/\/ve(j)=Max { ve(i)+dut(<i,j>) }
\n}
\n}
\nfor(i=0;i<vex;i++)
\ncout<<\"[\"<<i<<\"]-\"<<ve<<\" \";
\n}
\nvoid make_vl()
\n{
\ncout<<endl<<\"\u4e8b\u4ef6\u7684\u6700\u8fdf\u5f00\u59cb\u65f6\u95f4\uff1a\";
\nint i,j;
\nint a1,a2,a3;
\nvl[vex-1]=ve[vex-1];\/\/\u6c47\u70b9\u7684vl\u503c\u7b49\u4e8e\u5176ve\u503c
\nfor(i=vex-1;i>0;i--)\/\/\u6309\u9006\u62d3\u6251\u5e8f\u5217\u7684\u987a\u5e8f\u505a
\n{
\na1=tuopu;
\nfor(j=0;j<label_1[a1][1];j++)\/\/\u4ece\u6c47\u70b9\u5230\u6e90\u70b9\u63a8\u8fdb
\n{
\na2=linjie_1[a1][j];\/\/\u5411\u524d\u90bb\u63a5\u9876\u70b9
\na3=juzhen[a2][a1];\/\/\u8fb9\u7684\u6743\u503c
\nif(vl[a2]>vl[a1]-a3)
\nvl[a2]=vl[a1]-a3;\/\/vl(i)=Min { vl(j)-dut(<i,j>) }
\n}
\n}
\nfor(i=0;i<vex;i++)
\ncout<<\"[\"<<i<<\"]-\"<<vl<<\" \";
\n}
\nvoid critical_path()
\n{
\ncout<<endl<<\"\u5173\u952e\u8def\u5f84\uff1a\";
\nint i,j;
\nfor(i=0;i<vex;i++)
\nfor(j=0;j<vex;j++)
\n{
\nif(juzhen[j]!=max)
\n{
\ne[j]=ve;\/\/e(i)=ve(i)
\nl[j]=vl[j]-juzhen[j];\/\/l(i)=vl(j)-dut(<i,j>)
\nif(e[j]==l[j] && e[j]!=max)\/\/\u5173\u952e\u8def\u5f84\u7684\u5224\u65ad
\ncout<<\"[\"<<i<<\"]\"<<\"-->\"<<\"[\"<<j<<\"]\u00a0 \u00a0\u00a0\u00a0\";
\n}
\n}
\n}<\/p><\/blockquote>\n

ysfeng(\u6e38\u5ba2)\u53d1\u8868\u8bc4\u8bba\u4e8e2007-4-23 15:34:04\u5934\u4e24\u4e2a\u5e93\u51fd\u6570\u600e\u4e48\u6ca1\u6709\u5217\u51fa\uff1f
\n\u4ee5\u4e0b\u4e3ablog\u4e3b\u4eba\u7684\u56de\u590d\uff1a
\n\u56e0\u4e3a\u5b57\u4f53\u7684\u539f\u56e0\uff0c\u53ef\u80fd\u7f16\u8bd1\u5668\u8ba4\u4e0d\u51fa\u6765\u5427<\/p>\n","protected":false},"excerpt":{"rendered":"

#include<iostream.h> #include<cstdlib> #def...<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[28325],"tags":[],"class_list":["post-631","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/posts\/631","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=631"}],"version-history":[{"count":2,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/posts\/631\/revisions"}],"predecessor-version":[{"id":645,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=\/wp\/v2\/posts\/631\/revisions\/645"}],"wp:attachment":[{"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=631"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=631"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lnmp.ivan.xin\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=631"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}