• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0
            網(wǎng)絡流最大流問題。將顧客看做結(jié)點,另外增加一個源點和匯點,構(gòu)圖方式如下:源點和每個豬圈的第一個顧客連邊,權(quán)值為初始時豬圈中豬的數(shù)目;每個顧客和匯點連一條邊,權(quán)值為希望購買的豬的數(shù)目;如果顧客j緊跟著顧客i打開某個豬圈,那么結(jié)點i和結(jié)點j之間連一條邊,權(quán)值為kInf。
            以下是我的代碼:
            #include<queue>
            #include
            <algorithm>
            #include
            <cstdio>
            #include
            <cstring>
            using namespace std;
            const int kMaxn(107);
            const int kMaxpig(1007);
            const int kInf(0x7f7f7f7f);

            int pig,custom,r[kMaxpig],last[kMaxpig];
            int n,source,sink,maxflow,cap[kMaxn][kMaxn],flow[kMaxn][kMaxn];

            void SAP()
            {
                
            int d[kMaxn],num[kMaxn],p[kMaxn];

                memset(flow,
            0,kMaxn*kMaxn*sizeof(int));
                memset(d,
            0x7f,kMaxn*sizeof(int));
                memset(num,
            0,kMaxn*sizeof(int));
                queue
            <int> q;
                d[sink]
            =0;
                num[
            0]++;
                q.push(sink);
                
            while(!q.empty())
                {
                    
            int v(q.front());q.pop();
                    
            for(int u=1;u<=n;u++)
                        
            if(d[u]>=&& cap[u][v]>flow[u][v])
                        {
                            d[u]
            =d[v]+1;
                            num[d[u]]
            ++;
                            q.push(u);
                        }
                }

                maxflow
            =0;
                
            int u(source),v;
                
            while(d[source]<n)
                {
                    v
            =-1;
                    
            for(int i=1;i<=n;i++)
                        
            if(cap[u][i]>flow[u][i] && d[u]==d[i]+1)
                        {
                            v
            =i;break;
                        }
                    
            if(v!=-1)
                    {
                        p[v]
            =u;u=v;
                        
            if(u==sink)
                        {
                            
            int add(kInf);
                            
            for(u=sink;u!=source;u=p[u])
                                add
            =min(add,cap[p[u]][u]-flow[p[u]][u]);
                            maxflow
            +=add;
                            
            for(u=sink;u!=source;u=p[u])
                            {
                                flow[p[u]][u]
            +=add;
                                flow[u][p[u]]
            -=add;
                            }
                        }
                    }
                    
            else
                    {
                        num[d[u]]
            --;
                        
            if(!num[d[u]])
                            
            return;
                        d[u]
            =n;
                        
            for(v=1;v<=n;v++)
                            
            if(cap[u][v]>flow[u][v])
                                d[u]
            =min(d[u],d[v]+1);
                        num[d[u]]
            ++;
                        
            if(u!=source)
                            u
            =p[u];
                    }
                }
            }

            int main()
            {
                scanf(
            "%d%d",&pig,&custom);
                source
            =custom+1;
                sink
            =custom+2;
                n
            =custom+2;
                memset(cap,
            0,kMaxn*kMaxn*sizeof(int));
                
            for(int i=1;i<=pig;i++)
                    scanf(
            "%d",&r[i]);
                memset(last,
            0,kMaxpig*sizeof(int));
                
            for(int i=1;i<=custom;i++)
                {
                    
            int a,b;
                    scanf(
            "%d",&a);
                    
            for(int j=1;j<=a;j++)
                    {
                        
            int t;
                        scanf(
            "%d",&t);
                        
            if(last[t]==0)
                        {
                            last[t]
            =i;
                            cap[source][i]
            +=r[t];
                        }
                        
            else
                        {
                            cap[last[t]][i]
            =kInf;
                            last[t]
            =i;
                        }
                    }
                    scanf(
            "%d",&b);
                    cap[i][sink]
            +=b;
                }

                SAP();

                printf(
            "%d\n",maxflow);

                
            return 0;
            }
            posted on 2011-05-31 20:35 lee1r 閱讀(213) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:圖論
            久久久久国色AV免费看图片| 热re99久久精品国产99热| 久久青青草原精品国产软件| 久久久久无码精品| 99久久精品免费看国产一区二区三区| 久久久久亚洲国产| 97精品久久天干天天天按摩| 久久精品国产99久久久香蕉| 精品久久久无码21p发布| 久久精品国产精品亚洲精品| 狠狠色丁香久久婷婷综合_中| 久久精品99久久香蕉国产色戒| 成人国内精品久久久久影院VR| 欧美日韩精品久久久久| 国产精品永久久久久久久久久| 久久久久亚洲AV无码网站| 久久久久九九精品影院| 国产精品久久久久久一区二区三区| 久久最新免费视频| 国产—久久香蕉国产线看观看| 麻豆成人久久精品二区三区免费 | 精品国产一区二区三区久久蜜臀| 日日狠狠久久偷偷色综合96蜜桃| 狠狠色丁香久久婷婷综合五月| 婷婷久久综合| 国产一久久香蕉国产线看观看| 伊人久久大香线蕉AV色婷婷色| 欧美国产成人久久精品| 久久国产成人午夜aⅴ影院 | 国产成人无码精品久久久久免费| 久久夜色精品国产噜噜麻豆| 亚洲AV无码久久寂寞少妇| 一日本道伊人久久综合影| 欧美午夜A∨大片久久| 久久国产香蕉一区精品| 久久se精品一区精品二区国产| 9999国产精品欧美久久久久久| 精品久久久久久国产三级| 久久久精品久久久久久 | 久久久久99精品成人片欧美| 中文字幕乱码久久午夜|