{"id":191,"date":"2010-03-27T01:41:00","date_gmt":"2010-03-26T17:41:00","guid":{"rendered":"http:\/\/localhost\/?p=191"},"modified":"2010-03-27T01:41:00","modified_gmt":"2010-03-26T17:41:00","slug":"noi2006_maximum_profit","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=191","title":{"rendered":"[NOI2006]\u6700\u5927\u83b7\u5229"},"content":{"rendered":"\n<p>[NOI2006]\u6700\u5927\u83b7\u5229<\/p>\n<p>Time Limit:5000MS&#160; Memory Limit:65536K<br \/>Total Submit:65 Accepted:36 <br \/>Case Time Limit:1000MS<\/p>\n<p><strong>Description <\/strong><\/p>\n<p> \u65b0\u7684\u6280\u672f\u6b63\u51b2\u51fb\u7740\u624b\u673a\u901a\u8baf\u5e02\u573a\uff0c\u5bf9\u4e8e\u5404\u5927\u8fd0\u8425\u5546\u6765\u8bf4\uff0c\u8fd9\u65e2\u662f\u673a\u9047\uff0c\u66f4\u662f\u6311\u6218\u3002THU\u96c6\u56e2\u65d7\u4e0b\u7684CS&amp;T\u901a\u8baf\u516c\u53f8\u5728\u65b0\u4e00\u4ee3\u901a\u8baf\u6280\u672f\u8840\u6218\u7684\u524d\u591c\uff0c\u9700\u8981 \u505a\u592a\u591a\u7684\u51c6\u5907\u5de5\u4f5c\uff0c\u4ec5\u5c31\u7ad9\u5740\u9009\u62e9\u4e00\u9879\uff0c\u5c31\u9700\u8981\u5b8c\u6210\u524d\u671f\u5e02\u573a\u7814\u7a76\u3001\u7ad9\u5740\u52d8\u6d4b\u3001\u6700\u4f18\u5316\u7b49\u9879\u76ee\u3002 <br \/>\u5728\u524d\u671f\u5e02\u573a\u8c03\u67e5\u548c\u7ad9\u5740\u52d8\u6d4b\u4e4b\u540e\uff0c\u516c\u53f8\u5f97\u5230\u4e86\u4e00\u5171N\u4e2a\u53ef\u4ee5\u4f5c\u4e3a\u901a\u8baf\u4fe1\u53f7\u4e2d\u8f6c\u7ad9\u7684\u5730\u5740\uff0c\u800c\u7531\u4e8e\u8fd9\u4e9b\u5730\u5740\u7684\u5730\u7406\u4f4d\u7f6e\u5dee\u5f02\uff0c\u5728\u4e0d\u540c\u7684\u5730\u65b9\u5efa\u9020\u901a\u8baf\u4e2d\u8f6c\u7ad9\u9700 \u8981\u6295\u5165\u7684\u6210\u672c\u4e5f\u662f\u4e0d\u4e00\u6837\u7684\uff0c\u6240\u5e78\u5728\u524d\u671f\u8c03\u67e5\u4e4b\u540e\u8fd9\u4e9b\u90fd\u662f\u5df2\u77e5\u6570\u636e\uff1a\u5efa\u7acb\u7b2ci\u4e2a\u901a\u8baf\u4e2d\u8f6c\u7ad9\u9700\u8981\u7684\u6210\u672c\u4e3aPi\uff081\u2264i\u2264N\uff09\u3002 <br \/>\u53e6\u5916\u516c\u53f8\u8c03\u67e5\u5f97\u51fa\u4e86\u6240\u6709\u671f\u671b\u4e2d\u7684\u7528\u6237\u7fa4\uff0c\u4e00\u5171M\u4e2a\u3002\u5173\u4e8e\u7b2ci\u4e2a\u7528\u6237\u7fa4\u7684\u4fe1\u606f\u6982\u62ec\u4e3aAi,  Bi\u548cCi\uff1a\u8fd9\u4e9b\u7528\u6237\u4f1a\u4f7f\u7528\u4e2d\u8f6c\u7ad9Ai\u548c\u4e2d\u8f6c\u7ad9Bi\u8fdb\u884c\u901a\u8baf\uff0c\u516c\u53f8\u53ef\u4ee5\u83b7\u76caCi\u3002\uff081\u2264i\u2264M, 1\u2264Ai, Bi\u2264N\uff09 <br \/>THU\u96c6\u56e2\u7684CS&amp;T\u516c\u53f8\u53ef\u4ee5\u6709\u9009\u62e9\u7684\u5efa\u7acb\u4e00\u4e9b\u4e2d\u8f6c\u7ad9\uff08\u6295\u5165\u6210\u672c\uff09\uff0c\u4e3a\u4e00\u4e9b\u7528\u6237\u63d0\u4f9b\u670d\u52a1\u5e76\u83b7\u5f97\u6536\u76ca\uff08\u83b7\u76ca\u4e4b\u548c\uff09\u3002\u90a3\u4e48\u5982\u4f55\u9009\u62e9\u6700\u7ec8\u5efa\u7acb\u7684 \u4e2d\u8f6c\u7ad9\u624d\u80fd\u8ba9\u516c\u53f8\u7684\u51c0\u83b7\u5229\u6700\u5927\u5462\uff1f\uff08\u51c0\u83b7\u5229 = \u83b7\u76ca\u4e4b\u548c &#8211; \u6295\u5165\u6210\u672c\u4e4b\u548c\uff09 <\/p>\n<p><strong>Input <\/strong><\/p>\n<p> \u8f93\u5165\u6587\u4ef6\u4e2d\u7b2c\u4e00\u884c\u6709\u4e24\u4e2a\u6b63\u6574\u6570N\u548cM \u3002 <br \/>\u7b2c\u4e8c\u884c\u4e2d\u6709N\u4e2a\u6574\u6570\u63cf\u8ff0\u6bcf\u4e00\u4e2a\u901a\u8baf\u4e2d\u8f6c\u7ad9\u7684\u5efa\u7acb\u6210\u672c\uff0c\u4f9d\u6b21\u4e3aP1, P2, \u2026, PN \u3002 <br \/>\u4ee5\u4e0bM\u884c\uff0c\u7b2c(i + 2)\u884c\u7684\u4e09\u4e2a\u6570Ai, Bi\u548cCi\u63cf\u8ff0\u7b2ci\u4e2a\u7528\u6237\u7fa4\u7684\u4fe1\u606f\u3002 <br \/>\u6240\u6709\u53d8\u91cf\u7684\u542b\u4e49\u53ef\u4ee5\u53c2\u89c1\u9898\u76ee\u63cf\u8ff0\u3002 <\/p>\n<p><strong>Output <\/strong><\/p>\n<p> \u4f60\u7684\u7a0b\u5e8f\u53ea\u8981\u5411\u8f93\u51fa\u6587\u4ef6\u8f93\u51fa\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u516c\u53f8\u53ef\u4ee5\u5f97\u5230\u7684\u6700\u5927\u51c0\u83b7\u5229\u3002 <\/p>\n<p><strong>Sample Input <\/strong><\/p>\n<p>5 5<br \/>1 2 3 4 5<br \/>1 2 3<br \/>2 3 4<br \/>1 3 3<br \/>1 4 2<br \/>4 5 3<\/p>\n<p><strong>Sample Output <\/strong><\/p>\n<p>4<\/p>\n<p><strong>Hint <\/strong><\/p>\n<p> \u3010\u6837\u4f8b\u8bf4\u660e\u3011 <br \/>\u9009\u62e9\u5efa\u7acb1\u30012\u30013\u53f7\u4e2d\u8f6c\u7ad9\uff0c\u5219\u9700\u8981\u6295\u5165\u6210\u672c6\uff0c\u83b7\u5229\u4e3a10\uff0c\u56e0\u6b64\u5f97\u5230\u6700\u5927\u6536\u76ca4\u3002 <br \/>\u3010\u8bc4\u5206\u65b9\u6cd5\u3011 <br \/>\u672c\u9898\u6ca1\u6709\u90e8\u5206\u5206\uff0c\u4f60\u7684\u7a0b\u5e8f\u7684\u8f93\u51fa\u53ea\u6709\u548c\u6211\u4eec\u7684\u7b54\u6848\u5b8c\u5168\u4e00\u81f4\u624d\u80fd\u83b7\u5f97\u6ee1\u5206\uff0c\u5426\u5219\u4e0d\u5f97\u5206\u3002 <br \/>\u3010\u6570\u636e\u89c4\u6a21\u548c\u7ea6\u5b9a\u3011 <br \/>80%\u7684\u6570\u636e\u4e2d\uff1aN\u2264200\uff0cM\u22641 000\u3002 <br \/>100%\u7684\u6570\u636e\u4e2d\uff1aN\u22645 000\uff0cM\u226450 000\uff0c0\u2264Ci\u2264100\uff0c0\u2264Pi\u2264100\u3002 <\/p>\n<p><strong>Source <\/strong><\/p>\n<p>\u6211\u6655\u3002\u3002\u6211\u4ee5\u524d\u7684SAP\u5199\u6cd5\u90fd\u662f\u9519\u7684\uff1fzkw\u7684\u7a0b\u5e8f\u5c45\u7136\u662f\u9519\u7684\u56e7\u3002\u3002\u4e0d\u8fc7\u60b2\u5267\u7684\u662f\u4ee5\u524d\u7684\u6240\u6709\u9898\u76ee\u600e\u4e48\u90fd\u80fd\u8fc7\u56e7\u3002\u3002NOI\u7684\u6570\u636e\u679c\u7136\u662fNB\u989d\u3002\u3002<br \/>\u5373\u4f7f\u589e\u5e7f\u8fc7\u4e86\u8fb9\u5bb9\u91cf\u5df2\u7ecf\u662f0\u4e86\u8fd8\u8981\u66f4\u65b0\u9ad8\u5ea6\uff1f\u6211\u89c9\u5f97\u6ca1\u9053\u7406\u554a\u3002\u3002\u4e0d\u8fc7\u4e0d\u8fd9\u6837\u5c31\u4e0d\u80fdAC\u3002\u771f\u662f\u6d3b\u89c1\u9b3c\u56e7\u3002\u3002<br \/>Code\uff1a<br \/>#include&lt;cstdio&gt;<br \/>#include&lt;algorithm&gt;<br \/>#include&lt;iostream&gt;<br \/>#define rep(i,n) for(int i=0;i&lt;n;i++)<br \/>using namespace std;<br \/>const int maxn=60000,inf=~0U&gt;&gt;1;<br \/>struct Edge<br \/>{<br \/>    int t,c;<br \/>    Edge(int _t,int _c,Edge* _next):<br \/>        t(_t),next(_next),c(_c){}<br \/>    Edge*next,*op;<br \/>}*E[maxn]={0};<br \/>int n,m,vs,vt,v,Ans=0;<br \/>void InsEdge(int s,int t,int c)<br \/>{<br \/>    E[s]=new Edge(t,c,E[s]);<br \/>    E[t]=new Edge(s,0,E[t]);<br \/>    E[s]-&gt;op=E[t];E[t]-&gt;op=E[s];<br \/>}<br \/>inline int T(int i){return i;}<br \/>inline int C(int i){return n+i;}<br \/>void Init()<br \/>{<br \/>    scanf(&quot;%d%d&quot;,&amp;n,&amp;m);int s,t,c;<br \/>    v=n+m+2;vs=v-1;vt=v-2;<br \/>    rep(i,n)scanf(&quot;%d&quot;,&amp;c),InsEdge(T(i),vt,c);<br \/>    rep(i,m)<br \/>    {<br \/>        scanf(&quot;%d%d%d&quot;,&amp;s,&amp;t,&amp;c);&#8211;s;&#8211;t;<br \/>        InsEdge(C(i),T(s),inf);<br \/>        InsEdge(C(i),T(t),inf);<br \/>        InsEdge(vs,C(i),c);<br \/>        Ans+=c;<br \/>    }<br \/>}<br \/>int h[maxn],vh[maxn];<br \/>int aug(int no,int m)<br \/>{<br \/>    if(no==vt) return m;<br \/>    int l=m,minh=v;<br \/>    for(Edge*i=E[no];i;i=i-&gt;next)if(i-&gt;c)<br \/>    {<br \/>        if(h[no]==h[i-&gt;t]+1)<br \/>        {<br \/>            int d=aug(i-&gt;t,min(l,i-&gt;c));<br \/>            i-&gt;c-=d,i-&gt;op-&gt;c+=d,l-=d;<br \/>            if(!l||h[vs]&gt;=v) return m-l;<br \/>        }<br \/>        minh=min(minh,h[i-&gt;t]+1);<br \/>    }<br \/>    if(!&#8211;vh[h[no]]) h[vs]=v;<br \/>    vh[h[no]=minh]++;<br \/>    return m-l;<br \/>}<br \/>int CalFlow()<br \/>{<br \/>    memset(h,0,sizeof(h));<br \/>    memset(vh,0,sizeof(vh));<br \/>    vh[0]=v;int flow=0;<br \/>    while(h[vs]&lt;v) flow+=aug(vs,inf);<br \/>    return flow;<br \/>}<br \/>int main()<br \/>{<br \/>    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);<br \/>    Init();<br \/>    cout&lt;&lt;Ans-CalFlow()&lt;&lt;endl;<br \/>} <\/p>\n","protected":false},"excerpt":{"rendered":"<p>[NOI2006]\u6700\u5927\u83b7\u5229 Time Limit:5000MS&#160; Memory Limit:65536KTotal Submit:65 Accepted:36 Case Time Limit:1000MS Description \u65b0\u7684\u6280\u672f\u6b63\u51b2\u51fb\u7740\u624b\u673a\u901a\u8baf\u5e02\u573a\uff0c\u5bf9\u4e8e\u5404\u5927\u8fd0\u8425\u5546\u6765\u8bf4\uff0c\u8fd9\u65e2\u662f\u673a\u9047\uff0c\u66f4\u662f\u6311\u6218\u3002THU\u96c6\u56e2\u65d7\u4e0b\u7684CS&amp;T\u901a\u8baf\u516c\u53f8\u5728\u65b0\u4e00\u4ee3\u901a\u8baf\u6280\u672f\u8840\u6218\u7684\u524d\u591c\uff0c\u9700\u8981 \u505a\u592a\u591a\u7684\u51c6\u5907\u5de5\u4f5c\uff0c\u4ec5\u5c31\u7ad9\u5740\u9009\u62e9\u4e00\u9879\uff0c\u5c31\u9700\u8981\u5b8c\u6210\u524d\u671f\u5e02\u573a\u7814\u7a76\u3001\u7ad9\u5740\u52d8\u6d4b\u3001\u6700\u4f18\u5316\u7b49\u9879\u76ee\u3002 \u5728\u524d\u671f\u5e02\u573a\u8c03\u67e5\u548c\u7ad9\u5740\u52d8\u6d4b\u4e4b\u540e\uff0c\u516c\u53f8\u5f97\u5230\u4e86\u4e00\u5171N\u4e2a\u53ef\u4ee5\u4f5c\u4e3a\u901a\u8baf\u4fe1\u53f7\u4e2d\u8f6c\u7ad9\u7684\u5730\u5740\uff0c\u800c\u7531\u4e8e\u8fd9\u4e9b\u5730\u5740\u7684\u5730\u7406\u4f4d\u7f6e\u5dee\u5f02\uff0c\u5728\u4e0d\u540c\u7684\u5730\u65b9\u5efa\u9020\u901a\u8baf\u4e2d\u8f6c\u7ad9\u9700 \u8981\u6295\u5165\u7684\u6210\u672c\u4e5f\u662f\u4e0d\u4e00\u6837\u7684\uff0c\u6240\u5e78\u5728\u524d\u671f\u8c03\u67e5\u4e4b\u540e\u8fd9\u4e9b\u90fd\u662f\u5df2\u77e5\u6570\u636e\uff1a\u5efa\u7acb\u7b2ci\u4e2a\u901a\u8baf\u4e2d\u8f6c\u7ad9\u9700\u8981\u7684\u6210\u672c\u4e3aPi\uff081\u2264i\u2264N\uff09\u3002 \u53e6\u5916\u516c\u53f8\u8c03\u67e5\u5f97\u51fa\u4e86\u6240\u6709\u671f\u671b\u4e2d\u7684\u7528\u6237\u7fa4\uff0c\u4e00\u5171M\u4e2a\u3002\u5173\u4e8e\u7b2ci\u4e2a\u7528\u6237\u7fa4\u7684\u4fe1\u606f\u6982\u62ec\u4e3aAi, Bi\u548cCi\uff1a\u8fd9\u4e9b\u7528\u6237\u4f1a\u4f7f\u7528\u4e2d\u8f6c\u7ad9Ai\u548c\u4e2d\u8f6c\u7ad9Bi\u8fdb\u884c\u901a\u8baf\uff0c\u516c\u53f8\u53ef\u4ee5\u83b7\u76caCi\u3002\uff081\u2264i\u2264M, 1\u2264Ai, Bi\u2264N\uff09 THU\u96c6\u56e2\u7684CS&amp;T\u516c\u53f8\u53ef\u4ee5\u6709\u9009\u62e9\u7684\u5efa\u7acb\u4e00\u4e9b\u4e2d\u8f6c\u7ad9\uff08\u6295\u5165\u6210\u672c\uff09\uff0c\u4e3a\u4e00\u4e9b\u7528\u6237\u63d0\u4f9b\u670d\u52a1\u5e76\u83b7\u5f97\u6536\u76ca\uff08\u83b7\u76ca\u4e4b\u548c\uff09\u3002\u90a3\u4e48\u5982\u4f55\u9009\u62e9\u6700\u7ec8\u5efa\u7acb\u7684 \u4e2d\u8f6c\u7ad9\u624d\u80fd\u8ba9\u516c\u53f8\u7684\u51c0\u83b7\u5229\u6700\u5927\u5462\uff1f\uff08\u51c0\u83b7\u5229 = \u83b7\u76ca\u4e4b\u548c &#8211; \u6295\u5165\u6210\u672c\u4e4b\u548c\uff09 Input \u8f93\u5165\u6587\u4ef6\u4e2d\u7b2c\u4e00\u884c\u6709\u4e24\u4e2a\u6b63\u6574\u6570N\u548cM \u3002 \u7b2c\u4e8c\u884c\u4e2d\u6709N\u4e2a\u6574\u6570\u63cf\u8ff0\u6bcf\u4e00\u4e2a\u901a\u8baf\u4e2d\u8f6c\u7ad9\u7684\u5efa\u7acb\u6210\u672c\uff0c\u4f9d\u6b21\u4e3aP1, P2, \u2026, PN \u3002 \u4ee5\u4e0bM\u884c\uff0c\u7b2c(i + 2)\u884c\u7684\u4e09\u4e2a\u6570Ai, Bi\u548cCi\u63cf\u8ff0\u7b2ci\u4e2a\u7528\u6237\u7fa4\u7684\u4fe1\u606f\u3002 \u6240\u6709\u53d8\u91cf\u7684\u542b\u4e49\u53ef\u4ee5\u53c2\u89c1\u9898\u76ee\u63cf\u8ff0\u3002 Output \u4f60\u7684\u7a0b\u5e8f\u53ea\u8981\u5411\u8f93\u51fa\u6587\u4ef6\u8f93\u51fa\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u516c\u53f8\u53ef\u4ee5\u5f97\u5230\u7684\u6700\u5927\u51c0\u83b7\u5229\u3002 Sample Input 5 51 2 3 4 51 2 32 3 41 3 31 4 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/191"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=191"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/191\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=191"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}