[BZOJ2768][JLOI2010]冠军调查/[BZOJ1934/Luogu2057][SHOI2007]Vote 善意的投票(网络流)

发布于 2018-04-06  150 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2768][JLOI2010]冠军调查/[BZOJ1934/Luogu2057][SHOI2007]Vote 善意的投票(网络流)

Description

一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰,英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查,调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者,大家齐聚一堂,各抒己见。每一位参与者都将发言,阐述自己的看法。参与者的心里都有一个看法,比如FireDancer认为切尔西不可能夺冠,而WaterDancer认为切尔西一定问鼎。但是因为WaterDancer是FireDancer的好朋友,所以可能FireDancer为了迁就自己的好朋友,会在发言中支持切尔西。也就是说每个参与者发言时阐述的看法不一定就是心里所想的。现在告诉你大家心里的想法和参与者的朋友网,希望你能安排每个人的发言内容,使得违心说话的人的总数与发言时立场不同的朋友(对)的总数的和最小。

Tag

网络流

解决思路

为什么会有两个不同的年份的省选题一模一样?连样例都是一样的?很迷。
考虑把转化成最小割模型,那么,一个人如果违背自己的意愿,相当于是与原来所在的源点/汇点断开,连到另一边;而朋友立场不同,则说明两个人被割开。
那么建图,对每一个人向自己本来的意愿那一边连边,然后对每一对朋友连边,求最小割。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2768][JLOI2010]冠军调查/[BZOJ1934/Luogu2057][SHOI2007]Vote 善意的投票(网络流)


HNCJ OIer