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 阅读(1617) 评论(1)  编辑 收藏 引用

评论

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

在数组中insert,时间会更长  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理