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

            misschuer

            常用鏈接

            統計

            積分與排名

            百事通

            最新評論

            poj 3189 Steady Cow Assignment

            //題意 貌似是求滿意度的范圍最小.
            //順便貼個以前找到的, 效率還算可以的最大流模板

            #include 
            <cstdio>
            #include 
            <iostream>
            #include 
            <cstring>
            using namespace std;
            const int MAXV = 1210;
            const int MAXE = 1000010;
            const int inf = 1 << 29;

            int head[MAXV], N;

            struct Edge {
                
                
            int v, next, w;
            }edge[MAXE];

            int n, m, s, t, cnt, ans;

            void add(int u, int v, int w) {
                
                edge[cnt].v 
            = v;
                edge[cnt].w 
            = w;
                edge[cnt].next 
            = head[ u ];
                head[ u ] 
            = cnt++;
                
                edge[cnt].v 
            = u;
                edge[cnt].w 
            = 0;
                edge[cnt].next 
            = head[ v ];
                head[ v ] 
            = cnt++;
            }

            int sap() {
                
                
            int pre[MAXV], cur[MAXV], dis[MAXV], gap[MAXV];
                
            int flow = 0, aug = inf, u;
                
            bool flag;
                
                
            for(int i = 0; i <= N; ++ i) {
                    
                    cur[ i ] 
            = head[ i ];
                    gap[ i ] 
            = dis[ i ] = 0;
                }
                
                gap[ s ] 
            = N;
                u 
            = pre[ s ] = s;
                
                
            while(dis[ s ] < N) {
                    
                    flag 
            = 0;
                    
                    
            for(int &= cur[ u ]; j != -1; j = edge[ j ].next) {
                        
                        
            int v = edge[ j ].v;
                        
                        
            if(edge[ j ].w > 0 && dis[ u ] == dis[ v ] + 1) {
                            
                            flag 
            = 1;
                            
                            
            if(edge[ j ].w < aug) aug = edge[ j ].w;
                            
                            pre[ v ] 
            = u;
                            u 
            = v;
                            
                            
            if(u == t) {
                                
                                flow 
            += aug;
                                
                                
            while(u != s) {
                                    
                                    u 
            = pre[ u ];
                                    edge[cur[ u ]  ].w 
            -= aug;
                                    edge[cur[ u ]
            ^1].w += aug;
                                }
                                aug 
            = inf;
                            }
                            
            break;
                        }
                    }
                    
                    
            if(flag) continue;
                    
                    
            int mindis = N;
                    
                    
            for(int k = head[ u ]; k != -1; k = edge[ k ].next) {
                        
                        
            int v = edge[ k ].v;
                        
                        
            if(edge[ k ].w > 0 && dis[ v ] < mindis) {
                            
                            mindis 
            = dis[ v ];
                            cur[ u ] 
            = k;
                        }
                    }
                    
                    
            if( (--gap[dis[ u ]]) == 0break;
                    
                    dis[ u ] 
            = mindis + 1;
                    gap[dis[ u ]] 
            ++;
                    u 
            = pre[ u ];
                }
                
            return flow;
            }

            int cap[30], i, j;
            int mat[MAXV][30];

            int main() {
                
                
            while(scanf("%d %d"&m, &n) != EOF) {
                    
                    
            for(i = 1; i <= m; ++ i) {
                        
                        
            for(j = 1; j <= n; ++ j) {
                            
                            scanf(
            "%d"&mat[ i ][ j ]);
                        }
                    }
                    
                    
            for(i = 1; i <= n; ++ i) {
                        
                        scanf(
            "%d"&cap[ i ]);
                    }
                    
                    
            int left = 1, right = 1int mmax = n;
                    
                    
            while(left <= n && right <= n) {
                        
                        
                        s 
            = 0; t = m + n + 1; cnt = 0; N = t + 1;
                        memset(head,
            -1,sizeof(head));
                        
                        
            for(i = 1; i <= m; ++ i) {
                            
                            add(s, i, 
            1);
                        }
                        
                        
            for(i = 1; i <= m; ++ i) {
                            
                            
            for(j = 1; j <= n; ++ j) {
                                
                                
            if(left <= j && j <= right) {
                                    
                                    add(i, mat[ i ][ j ]
            +m, 1);
                                }
                            }
                        }
                        
                        
            for(j = 1; j <= n; ++ j) {
                            
                            add(m
            +j, t, cap[ j ]);
                        }
                        
                        ans 
            = sap();
                        
                        
            if(ans == m) {
                            
                            
            if(mmax > right - left + 1) mmax = right - left + 1;
                            left 
            ++;
                        }
                        
            else right ++;
                    }
                    
                    printf(
            "%d\n", mmax);
                }
                
            return 0;
            }

            posted on 2011-03-24 11:05 此最相思 閱讀(146) 評論(0)  編輯 收藏 引用

            久久久久久久精品成人热色戒| 久久66热人妻偷产精品9| 国产精品免费久久久久久久久 | 麻豆亚洲AV永久无码精品久久| 亚洲精品高清一二区久久| 色偷偷88888欧美精品久久久 | 欧美精品乱码99久久蜜桃| 性欧美丰满熟妇XXXX性久久久| 九九久久99综合一区二区| 三级片免费观看久久| 国产精品久久波多野结衣| 欧美麻豆久久久久久中文| 精品永久久福利一区二区| 亚洲欧洲精品成人久久曰影片 | 婷婷综合久久狠狠色99h| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 亚洲精品无码久久久久sm| 一级做a爰片久久毛片16| 久久天天躁狠狠躁夜夜2020一| 久久国产精品-久久精品| 久久精品国产精品亚洲精品 | 久久综合久久久| 久久AV高潮AV无码AV| 久久人人爽人人爽人人片AV麻豆| 国产三级久久久精品麻豆三级| 久久亚洲精品成人无码网站| 国产成人久久久精品二区三区| 国内精品久久久久久久97牛牛| 国产精品久久久久久久人人看| 国产精品99久久久久久www| 秋霞久久国产精品电影院| 久久精品国产清高在天天线| 亚洲va久久久噜噜噜久久| 一97日本道伊人久久综合影院| 久久99精品国产麻豆蜜芽| 久久国产一区二区| 国产精品久久久久9999| 国产精品久久精品| 色综合久久久久网| 久久久久九九精品影院| 亚洲国产精品嫩草影院久久|