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

            The Fourth Dimension Space

            枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

            [POI2005]Kos-Dicing 二分+最大流

            原來網絡流也能二分,今天終于見識了。。。
            二分+最大流
            題目大意:給定n個人m場比賽,問贏的最多的人最少贏幾場
             二分答案,增加源匯點,左邊一排是比賽點,右邊是球員,若有比賽,比賽向倆球員連容量為1的邊
            源點向比賽連容量為1的邊,球員向匯點連容量為二分枚舉值的邊,判斷是最大流是否等于比賽個數

            網絡流的構圖真是個神奇的東西,我承認如果不看網上的解題報告,我真的很難想到,首先是題意不太明確,剛開始我還以為贏的最多的選手勝利的場次必須是最多的。。。但是從樣例來看,貌似就算每個人都贏一場也會有冠軍出現。。。說說我的理解吧,從超級源點引一條邊至代表每場比賽的節點,限制每場比賽的勝利者只有一個人,這個流量如果在射出到某個選手的一條邊中,代表這場比賽是他取勝。每個選手到匯點連一條二分枚舉的邊,就是限制勝利場次的上界,如果最后的最大流等于m,說明這m場比賽的的勝者可以合理的分配,如果不能,說明比賽不能正常進行。又可以分析得出,如果某一個二分值mid滿足要求,那么比他大的值一定也滿足要求。故可二分枚舉答案。(PS:這題的復雜度應該是(10000+10000+2)^2*(m*2+m+n)*log 10000.總覺得要超時啊。。。難道數據弱了?)

            int n,m;

            struct node2
            {
                
            int a,b;
            }
            re[100000];

            bool check(int n,int m,int mid)
            {
                
            int i;
                
            for(i=0;i<n+m+2;i++)
                    adj[i]
            =NULL;
                len
            =0;
                
            int s=n+m;
                
            int t=s+1;
                
            for(i=0;i<m;i++)
                    insert(s,i,
            1);
                
            for(i=0;i<n;i++)
                    insert(m
            +i,t,mid);
                
            for(i=0;i<m;i++)
                
            {
                    insert(i,m
            +re[i].a,1);
                    insert(i,m
            +re[i].b,1);
                }

                
            return dinic(t+1,s,t)==m;
            }


            int main()
            {
                
            int i;
                
            while(scanf("%d%d",&n,&m)!=EOF)
                
            {
                    
            for(i=0;i<m;i++)
                    
            {
                        scanf(
            "%d%d",&re[i].a,&re[i].b);
                        re[i].a
            --;
                        re[i].b
            --;
                    }

                    
            int l=1,r=m;
                    
            int ans=-1;
                    
            while(l<=r)
                    
            {

                        
            int mid=(l+r)>>1;
                        
            if(check(n,m,mid))
                        
            {
                            ans
            =mid;
                            r
            =mid-1;
                        }

                        
            else
                            l
            =mid+1;
                    }

                    printf(
            "%d\n",ans);
                }

                
            return 0;


            }

            posted on 2010-07-17 20:43 abilitytao 閱讀(1644) 評論(1)  編輯 收藏 引用

            評論

            # re: [POI2005]Kos-Dicing 二分+最大流[未登錄] 2010-07-19 11:13 1

            在數組中insert,時間會更長  回復  更多評論   

            久久国产三级无码一区二区| 久久99久久99小草精品免视看| 久久国产一区二区| 国产叼嘿久久精品久久| 久久婷婷午色综合夜啪| 亚洲va久久久噜噜噜久久天堂| 久久最近最新中文字幕大全| 日韩AV毛片精品久久久| 精品永久久福利一区二区| 久久精品国产精品亚洲下载| 亚洲香蕉网久久综合影视 | 91精品国产高清久久久久久国产嫩草 | 久久99免费视频| 亚洲人成无码网站久久99热国产 | 91精品国产91久久久久久青草 | 精品国产乱码久久久久久1区2区| 国产成人AV综合久久| 欧美一区二区三区久久综合| 久久久久国产日韩精品网站| 久久er热视频在这里精品| 亚洲国产精品无码久久| 亚洲精品综合久久| 国产69精品久久久久99尤物| 久久精品aⅴ无码中文字字幕重口 久久精品a亚洲国产v高清不卡 | 亚洲午夜福利精品久久| 久久国产精品久久国产精品| 亚洲精品无码久久久久sm| 日本精品久久久久影院日本| 精品乱码久久久久久夜夜嗨| 久久国产高清字幕中文| 精品久久久久久亚洲精品 | 久久人人爽人人爽人人片AV麻烦 | 青青国产成人久久91网| 99久久人妻无码精品系列蜜桃| 久久久久青草线蕉综合超碰| 久久久久人妻一区精品| 久久精品亚洲福利| 色偷偷88欧美精品久久久| 久久久久久久综合狠狠综合| 精品熟女少妇AV免费久久| 伊人久久综合无码成人网|