• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            pku2135 Farm Tour 經典最小費用流

            不說什么,求a到b的兩條不相交路徑,使得總費用最少。你懂的。。(話說。。第一次手寫最少費用流,以前都直接Ctrl+A,Ctrl+C,Ctrl+V直接模板~)
            代碼:
             1 # include <cstdio>
             2 # include <cstring>
             3 # include <cstdlib>
             4 using namespace std;
             5 struct node
             6 {
             7    int p,c,e,s,nxt;
             8 }edge[50000];
             9 int g[1005],cc=0,n,m;
            10 void insert(int s,int e,int c,int p)
            11 {
            12    edge[cc].p=p;
            13    edge[cc].nxt=g[s];
            14    edge[cc].e=e;
            15    edge[cc].s=s;
            16    edge[cc++].c=c;
            17    edge[cc].p=-p;
            18    edge[cc].nxt=g[e];
            19    edge[cc].e=s;
            20    edge[cc].s=e;
            21    edge[cc++].c=0;
            22 };
            23 int pre[1005];
            24 int min(int a,int b)
            25 {
            26     return a<b?a:b;
            27 }
            28 int callen(int s,int e)
            29 {
            30     int len[1005];
            31     memset(len,-1,sizeof(len));
            32     len[s]=0;
            33     for(int i=0;i<n+2;i++)
            34       for(int j=0;j<cc;j++)
            35         if(edge[j].c>0&&len[edge[j].s]!=-1&&(len[edge[j].e]==-1||len[edge[j].e]>len[edge[j].s]+edge[j].p))
            36           len[edge[j].e]=len[edge[j].s]+edge[j].p,pre[edge[j].e]=j;
            37    return len[e];
            38 }
            39 int calmin(int s,int e)
            40 {
            41     if(e==s) return 0xfffffff;
            42     else return min(calmin(s,edge[pre[e]].s),edge[pre[e]].c);
            43 }
            44 void adjust(int s,int e,int minnum)
            45 {
            46      if(e==s) return;
            47      else
            48      {
            49          edge[pre[e]].c-=minnum;
            50          edge[pre[e]^1].c+=minnum;
            51          adjust(s,edge[pre[e]].s,minnum);
            52      }
            53 }
            54 int max_flow(int s,int e)
            55 {
            56     int p=0;
            57     while(true)
            58     {
            59         int len=callen(s,e);
            60         if(len==-1return p;
            61         else
            62         {
            63             int minnum=calmin(s,e);
            64             adjust(s,e,minnum);
            65             p+=minnum*len;
            66         }  
            67     }
            68 }
            69 int main()
            70 {
            71     int data[10000][3];
            72     scanf("%d%d",&n,&m);
            73     for(int i=0;i<m;i++)
            74       scanf("%d%d%d",&data[i][0],&data[i][1],&data[i][2]);
            75     int best=0xfffffff;
            76 
            77        cc=0
            78        insert(0,1,2,0);
            79        insert(n,n+1,2,0);
            80        for(int j=0;j<m;j++)
            81           insert(data[j][0],data[j][1],1,data[j][2]),insert(data[j][1],data[j][0],1,data[j][2]);
            82        int p=max_flow(0,n+1);
            83          best=min(best,p);
            84     
            85     printf("%d\n",best);
            86    // system("pause");
            87     return 0;
            88 }
            89 

            posted on 2011-03-13 02:29 yzhw 閱讀(277) 評論(1)  編輯 收藏 引用 所屬分類: graph

            評論

            # re: pku2135 Farm Tour 經典最小費用流[未登錄] 2011-03-26 17:55 viaxl

            早上我看你沒了我就呲啦把衛生巾撕了!
            結果中午你又來了一小點!
            好的 算我失誤!那我洗了短褲重新再把衛生巾墊上!
            一個下午你再沒影了那我又把衛生巾給撕了!
            結果晚上睡覺前我發現你又來了!我又要洗短褲了!
            這樣是不是很好玩!你說啊是不是很好玩!
            這不是洗多少短褲的問題!
            而是我和你之間的信任問題!!!!!  回復  更多評論   

            <2011年1月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久亚洲AV无码西西人体| 午夜精品久久久久久中宇| 99久久精品国产综合一区| 国产午夜福利精品久久| 久久久国产精品| 色综合久久无码五十路人妻| 久久精品国产亚洲AV电影 | 精品国产青草久久久久福利| 久久久久久噜噜精品免费直播| 久久强奷乱码老熟女| 久久精品人成免费| 美女久久久久久| 久久香综合精品久久伊人| 久久久久久国产精品免费免费| 伊人久久大香线蕉亚洲| 久久精品成人免费国产片小草| 久久久久久精品成人免费图片| 久久综合中文字幕| 日本久久久久亚洲中字幕| 久久久精品波多野结衣| 国产成人精品久久免费动漫| 欧美一区二区久久精品| 国产高潮久久免费观看| 日韩AV无码久久一区二区| 热RE99久久精品国产66热| 国产69精品久久久久99尤物| 久久精品亚洲中文字幕无码麻豆| 一本色综合久久| 精品久久久久久99人妻| 久久综合九色综合精品| 久久精品国产亚洲av影院| 久久这里有精品| 国产99久久久国产精品小说| 久久激情亚洲精品无码?V| 久久黄色视频| 亚洲精品tv久久久久| 久久这里有精品视频| 亚洲伊人久久综合中文成人网 | 久久精品中文无码资源站| 亚洲伊人久久成综合人影院| 亚洲精品tv久久久久|