The Fourth Dimension Space

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

[Shoi2007]Vote 善意的投票 网络流,最小割

题目大意:n个小朋友投票,定义投票的冲突数为好友间发生冲突数加上所有和自己意愿发生冲突的人数,求冲突最少数
分析:增加源汇点,s向所有同意的连容1的边,所有反对的向t连容1的边,若俩人是好友,则相互连容1边
对于经过好友间的流量,表示着冲突,即可用冲突或改变意愿来替代,那么最小割就成了冲突数的定义

看到网上的几个代码都进行了拆点,我觉得似乎没有必要,直接构图,AC.看来感觉是对的,但我有些疑惑的是为什么要把正反两条边都建起来,后来想了一下,其实最小割模型中有个偏序的关系,模型的一侧是包含s的一组结点,右侧是包含t的一组结点,而SET(S)到SET(T)应该是相连的,而如果建成单相边的话,有可能导致S,T之间没有路径存在。而最小割中恰好又只取S->T的边,所以无论关系是怎样的,都可以满足要求,取两个朋友之间的一条边,此题得解。

posted on 2010-07-17 14:17 abilitytao 阅读(1364) 评论(0)  编辑 收藏 引用


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