• <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>

            poj1273

            Drainage Ditches

            Time Limit: 1000MS Memory Limit: 10000K
            Total Submissions: 37500 Accepted: 13862

            Description

            Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
            Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
            Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

            Input

            The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

            Output

            For each case, output a single integer, the maximum rate at which water may emptied from the pond.

            Sample Input

            5 4
            1 2 40
            1 4 20
            2 4 20
            2 3 30
            3 4 10
            

            Sample Output

            50
            話說這是道網(wǎng)絡(luò)流的模版題,鄙人沒寫過多少網(wǎng)絡(luò)流,于是忍不住來練練手
            邪惡的是,我打了模版之后,才發(fā)現(xiàn)我模版好多錯(cuò)誤(自己改的模版),悲劇
            然后終于改好了,然后一直wa,
            不解,重邊我也處理了呀,怎么搞的,
            然后去看discuss,忽然發(fā)現(xiàn)一組數(shù)據(jù)
            input:
            3 2
            1 2 3
            1 2 4
            1 2 5
            output:
            12
            頓時(shí)無語了,原來重邊在這里要相加啊,我開始取得min,后來取得max
            呃,表示自己真心是水貨
              1#include<stdio.h>
              2#include<string.h>
              3#include<math.h>
              4#define MAX 205
              5#define inf 0x7fffffff
              6int n,m,s,t;
              7int map[MAX][MAX];
              8int d[MAX],r[MAX][MAX],num[MAX],pre[MAX];
              9int min(int a,int b)
             10{
             11    if(a<b) return a;
             12    else return b;
             13}

             14int void bfs()
             15{
             16    int i,k;
             17    int q[MAX*MAX],head,tail;
             18    for(i=1;i<=n;i++)
             19        d[i]=n+1;
             20    memset(num,0,sizeof(num));
             21    head=0;
             22    tail=1;
             23    q[tail]=t;
             24    d[t]=0;
             25    num[0]=1;
             26    while(head<tail)
             27    {
             28        head++;
             29        k=q[head];
             30        for(i=1; i<=n; i++)
             31        {
             32            if(d[i]>n&&r[i][k]>0)
             33            {
             34                d[i]=d[k]+1;
             35                tail++;
             36                q[tail]=i;
             37                num[d[i]]++;
             38            }

             39        }

             40    }

             41}

             42int findalowarc(int i)
             43{
             44    int j;
             45    for(j=1; j<=n; j++)
             46        if((r[i][j]>0)&&(d[i]==d[j]+1)) return j;
             47    return -1;
             48}

             49int relabel(int i)
             50{
             51    int j;
             52    int mm=inf;
             53    for(j=1; j<=n; j++)
             54    {
             55        if (r[i][j]>0) mm=min(mm,d[j]+1);
             56    }

             57    return (mm==inf)?n:mm;
             58}

             59int maxflow()
             60{
             61    int flow,i,j,delta;
             62    int x;
             63    bfs();
             64    i=s;
             65    flow=0;
             66    memset(pre,-1,sizeof(pre));
             67    while(d[s]<=n)
             68    {
             69        j=findalowarc(i);
             70        if(j>0)
             71        {
             72            pre[j]=i;
             73            i=j;
             74            if(i==t)
             75            {
             76                delta=inf;
             77                for(i=t; i!=s; i=pre[i])
             78                    delta=min(delta,r[pre[i]][i]);
             79                for(i=t; i!=s; i=pre[i])
             80                {
             81                    r[pre[i]][i]-=delta;
             82                    r[i][pre[i]]+=delta;
             83                }

             84                flow+=delta;
             85            }

             86        }

             87        else
             88        {
             89            x=relabel(i);
             90            num[x]++;
             91            num[d[i]]--;
             92            if(num[d[i]]==0return flow;//間隙優(yōu)化
             93            d[i]=x;
             94            if(i!=s) i=pre[i];
             95        }

             96    }

             97    return flow;
             98}

             99int main()
            100{
            101    int i,j;
            102    int x,y,z;
            103    while (scanf("%d%d",&m,&n)!=EOF)
            104    {
            105        s=1;
            106        t=n;
            107        memset(map,0,sizeof(map));
            108        for (i=1; i<=m; i++ )
            109        {
            110            scanf("%d%d%d",&x,&y,&z);
            111            if (map[x][y]==0)
            112            {
            113                map[x][y]=z;
            114            }

            115            else
            116            {
            117                map[x][y]=map[x][y]+z;
            118            }

            119        }

            120        for(i=1; i<=n; i++)
            121            for(j=1; j<=n; j++)
            122                r[i][j]=map[i][j];
            123        printf("%d\n",maxflow());
            124    }

            125    return 0;
            126}

            127
             還發(fā)現(xiàn)個(gè)問題
            我寫的sap怎么跑了16ms,同學(xué)寫的ek才跑了0ms
            why??

            posted on 2012-03-14 00:20 jh818012 閱讀(357) 評(píng)論(1)  編輯 收藏 引用

            評(píng)論

            # re: poj1273 2012-03-20 10:02 王私江

            哈哈哈,您弱爆了!!  回復(fù)  更多評(píng)論   


            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿

            文章檔案(85)

            搜索

            最新評(píng)論

            • 1.?re: poj1426
            • 我嚓,,輝哥,,居然搜到你的題解了
            • --season
            • 2.?re: poj3083
            • @王私江
              (8+i)&3 相當(dāng)于是 取余3的意思 因?yàn)?3 的 二進(jìn)制是 000011 和(8+i)
            • --游客
            • 3.?re: poj3414[未登錄]
            • @王私江
              0ms
            • --jh818012
            • 4.?re: poj3414
            • 200+行,跑了多少ms呢?我的130+行哦,你菜啦,哈哈。
            • --王私江
            • 5.?re: poj1426
            • 評(píng)論內(nèi)容較長,點(diǎn)擊標(biāo)題查看
            • --王私江
            97超级碰碰碰碰久久久久| 色婷婷综合久久久久中文字幕| 亚洲国产精品高清久久久| 国产成人无码精品久久久性色| 中文精品99久久国产| 无码国内精品久久人妻蜜桃| 亚洲国产精品18久久久久久| avtt天堂网久久精品| 97久久精品人人做人人爽| 三级韩国一区久久二区综合| 亚洲精品乱码久久久久久自慰| 国产精品久久久久国产A级| 99久久精品国产毛片| 国内精品久久国产| 色综合久久综合网观看| 欧美噜噜久久久XXX| 国产69精品久久久久观看软件 | 日本精品久久久久影院日本| 久久妇女高潮几次MBA| 久久亚洲AV永久无码精品| 久久精品九九亚洲精品| 亚洲日本va午夜中文字幕久久| 久久婷婷五月综合97色| 国内精品久久久久久麻豆| 久久最近最新中文字幕大全 | 国产成人精品综合久久久| 波多野结衣中文字幕久久| 亚洲精品综合久久| 99久久99久久精品国产片果冻| 亚洲欧美日韩久久精品第一区| 欧洲国产伦久久久久久久| 久久97久久97精品免视看秋霞| 国产人久久人人人人爽| 久久久噜噜噜久久中文福利| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 一级A毛片免费观看久久精品| 热久久国产精品| 免费观看成人久久网免费观看| 久久久久人妻一区精品色| 久久精品人人做人人爽97| 久久综合狠狠综合久久 |