The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

ZOJ 3348 Schedule 经典网络流构图模型

网络流
题目描述:已知之前的一些比赛双方和结果,和未来的赛事安排,问DD能否夺冠,不能并列
我们谈心的让未来DD参加的比赛都赢,且我们可以知道未来每个人最多可以赢几场
给所有选手编号,预先统计出所有选手已经胜利的场次,然后对所有还没有进行的比赛,假设其中任意一个选手获胜,并统计胜负关系,(加入每个人胜利的次数在w[]中,每两个选手互相对战胜利的次数在a[][]中)即某两个选手a,b进行比赛a赢b的次数和b赢a的次数,这里要注意的是两个选手进行比赛,你假设任意一个选手获胜都是正确的,待会你会发现其实假设仅仅只是假设。增加超级源超级汇,超级源向每一个结点射出一条容量是这个点胜利场次的边,所有的点向汇点连一条容量是w[ID[DD]]-1的边,显然是为了限制每个点的胜利次数不能大于等于DD.中间任意两个结点根据胜负关系建立一条容量是a[i][j]的边,跑一遍最大流即可,如果满流,说明有可行解,否则无解。
下面来分析一下构图的原理,超级源向所有选手连一条容量是他将要获胜场次的边,比如说是c,说明这个选手有c场胜利要分配,如果这条边上的流量直接流向了汇点,说明该选手获胜,如果流量通过有向边流向了他的对手,说明这个胜利果实被他的对手拿走了,也就是实际上输掉了比赛,所以我才说假设仅仅是假设。再加上有每个点到汇点的限流,跑一遍最大流如果能满流说明比赛可以合理的分配胜负关系使得每个人的胜利场次都不超过DD,如果不能,无解。
这题构图确实很精彩,赞!

posted on 2010-07-21 09:58 abilitytao 阅读(1472) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理