bzoj 1934: [Shoi2007]Vote 善意的投票 最小割 最大流 dinic

先说一下建图方式,然后说一下为什么这样子是对的。

对于每一个赞同的,我们从S连一条边到这个人,流量为1。对于每个不赞同的,我们从他连一条边到T,流量为1。对于每个PY关系我们都连一条双向边!注意是双向,然后流量都为1。然后对于这个图求一下最小割就是答案了。

我们来考虑一下为什么这么做是对的。最后所有人无非两种状态,赞同或不赞同,所有人分成了两个点集。一个人如果违背他最初的意愿,那么显然需要与他连得端点分离,造成1的冲突。一对PY关系如果得不到满足,也会造成1的冲突。而每一个冲突都对应一条边。

我们考虑,我们无非是要找最小冲突,就是破坏掉的边最少,就是最小割了。

开始读入PY关系用n来循环读,然后很惨的WA了一发。。。。

发表评论