自动搬运

查看原文

来自洛谷，原作者为

	ReZHUI **

搬运于2025-08-24 21:33:29，当前版本为作者最后更新于2019-05-25 12:22:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目： 幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。每位小朋友应该怎样投票，才能使冲突数最小？

---

算法建模分析

此题的关键是为什么小朋友之间要连双向边(这一点我将一步一步分析）

我们从关系出发，暂且不管冲突的事情 众所周知,图可以表示点与点之间的关系,这种关系即点之间的连线 分析题目可以得出两种关系： 1、好朋友间的关系 2、小朋友与立场的关系（同意或者不同意睡觉） 下面，我们就要依照这两种关系进行建模

对于立场的建模

首先,对于是否睡觉的问题，只有两种互斥的情况：同意 或者 不同意
显然，我们可以设置两个集合，将同意的小朋友和不同意的小朋友分别放入两个集合里

那么如何与网络流结合起来，就不言而喻了。

我们将同意的小朋友与源点相连

不同意的小朋友与汇点相连 (当然你也可以反过来连）

我们可以这样理解一条单向边的含义：

一条从A——>B的边，表示 A 要求 B 同它同立场

那么，如何判断一个小朋友究竟是在哪个集合里呢？ 我们将源点和汇点均称为立场点

（原谅我取名水平有限，主要是为了方便大家理解）

从立场点出发，凡是能到达的点都应持该立场

（注意，这个看似毫无用处的判断方式，将解决接下来的冲突问题）

对于好朋友间的建模

在此时我们引入冲突的概念

为什么要在此时引入冲突呢？

回顾一下题目

为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数

可以发现，发生冲突的两种情况与上述的两种关系是相对应的

1、违背自身的意愿

2、违背好朋友的意愿

---

关于第一种冲突，根本上是由于第二种冲突引起的

试想:假如这群小朋友间不存在好朋友关系，那么就不会存在任何冲突，因为不会违背好朋友的意愿，也不会为了和好朋友的立场保持一致而违背了自身的意愿

---

关于第二种冲突，是由于一对好朋友持不同的立场

换一种理解

(设有一对好朋友，小A 小B）

小A 要求 小B同自己一个立场 ，而小B要求小A同自己一个立场

（话说这就是小朋友的友谊啊，总是希望好朋友和自己保持一致）

由于小A，小B都要求对方改变立场，是不是就发生了冲突？

---

现在，我们再回到我们设定的单向边含义

一条从A——>B的边，表示 A 要求 B 同它同立场

那么为什么好朋友之间需要连双向边是不是就解决了？.........

好朋友互相要求对方同自己一个立场

关于这个问题，我们还可以多角度思考：

这里我们可以倒过来想： 倘若好朋友之间是单向边？那么本身图就是走不通的，也就不存在冲突了,显然不符

也可以从对称性的角度来看： A 与 B的朋友关系是相对的，单向边显然不符合对称性

---

解决冲突

由于，违背自己意愿的冲突根本上是由于好朋友之间的冲突

那么，解决冲突就必须先解决好朋友间的冲突

所以，如何解决好朋友间的冲突呢？——很简单，改变两人间任意一个人的立场

（ 即割掉好朋友间的一条边，一个人就不再要求另一个人的立场 ）

其次，如何解决违背自身的冲突呢？——无非也是割边，让自己不再被要求持该立场

如何付出最小的代价，就解决所有的冲突呢？所割的边容量之和最小。这就转化成最小割问题了。

根据最大流最小割定理 最小割等于最大流

(关于此定理的证明，这里不再赘述，请问度娘吧)

所以，建完图后跑一边最大流就完事了

献上蒟蒻的代码

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=200520;
int n,m,s,t,pos,tot=1,maxflow;
int vis[N],incf[N],pre[N],head[N],Next[N],ver[N],edge[N];
void add(int x,int y,int z){
   ver[++tot]=y;edge[tot]=z;Next[tot]=head[x];head[x]=tot;
   ver[++tot]=x;edge[tot]=0;Next[tot]=head[y];head[y]=tot;
}
bool bfs(){    
   memset(vis,0,sizeof(vis));vis[s]=1;
   queue<int> q;q.push(s);
   incf[s]=inf;
   while(q.size()){
       int x=q.front();q.pop();
       for(int i=head[x];i;i=Next[i])
           if(edge[i]){
           	int y=ver[i];
           	if(vis[y])continue;
           	incf[y]=min(incf[x],edge[i]);
           	pre[y]=i;
           	q.push(y);
           	vis[y]=1;
           	if(y==t)return 1;
       	}
   }
   return 0;
}
void update(){
   int x=t;
   while(x!=s){
       int i=pre[x];
       edge[i]-=incf[t];
       edge[i^1]+=incf[t];
       x=ver[i^1];
   }
   maxflow+=incf[t];
}
int main()
{
   //朋友间建双向边，反对和同意分别与源点和汇点相连，最小冲突即最小割，即最大流 
   ios::sync_with_stdio(false);
   cin>>n>>m;
   s=0,t=n+1;
 	for(int i=1;i<=n;i++){
 		cin>>pos;
 		if(pos)add(s,i,1);
 		else add(i,t,1);
     }
   for(int i=1;i<=m;i++){
       int x,y;
       cin>>x>>y;
       add(x,y,1);
       add(y,x,1); 
   } 
   while(bfs())update();
   cout<<maxflow<<endl;
   return 0;
}

本题是我写的网络流第三题（不算板子应该是第二题）

这也是本蒟蒻的第一篇题解（还真是意义巨大）也废了不少功夫

所以，如果看懂的话不妨点个赞， 算是对我的认可吧，也为了让更多和我一样被毒瘤的网络流困扰的萌新们看到~~~~

溜溜溜_________________________________________________________________________________________________________________________