Link

\(\text{Solution:}\)

我们令源点和汇点分别为睡觉和不睡觉这两种互斥的决策点。把小朋友看成点，问题转化为最小割。

每一个小朋友对自己的意愿指向的汇点/源点。容量为\(1.\)之后要处理好朋友之间的关系。

让我们回到最小割的定义：求一组边，使它们割掉后，\(S,T\)不连通。

注意，这里只是不连通，而不是直接没有边相连。

于是，我们可以对每一对小朋友建立双向边，因为他们之间的关系是对称的。而我们把他们划分到两个集合种，只需要割掉双向边中的一条，它们就已经不连通了。

于是，这个问题被成功建模。

总结：深度清晰理解什么是最小割。注意仅仅是\(S,T\)不连通即可。不是割掉所有边。这题的边都表示的是一种关系，如\(A\to B\)的意义是\(A\)和\(B\)在同一立场。

我们的目的是将\(S,T\)分开以求到一组可行解。这组解最小的代价就是我们要求的最小冲突数。

#include<bits/stdc++.h>using namespace std;const int MAXN=300010;const int inf=(1<<30);struct edge{ int nxt,to,flow;}e[MAXN];int n,m,head[MAXN],tot=1,S,T;inline void add(int x,int y,int w){ e[++tot].to=y;e[tot].nxt=head[x];e[tot].flow=w;head[x]=tot; e[++tot].to=x;e[tot].nxt=head[y];e[tot].flow=0;head[y]=tot;}int dep[MAXN],cur[MAXN];bool bfs(int s,int t){ memset(dep,0,sizeof(dep)); queue<int>q;q.push(s); dep[s]=1;cur[s]=head[s]; while(!q.empty()){ s=q.front();q.pop(); for(int i=head[s];i;i=e[i].nxt){ int j=e[i].to; if(!dep[j]&&e[i].flow){ dep[j]=dep[s]+1; cur[j]=head[j]; if(j==t)return true; q.push(j); } } } return false;}int dfs(int s,int flow,int t){ if(s==t||flow<=0)return flow; int rest=flow; for(int i=head[s];i;i=e[i].nxt){ int j=e[i].to; if(dep[j]==dep[s]+1&&e[i].flow){ int tmp=dfs(j,min(rest,e[i].flow),t); if(tmp<=0)dep[j]=0; rest-=tmp;e[i].flow-=tmp;e[i^1].flow+=tmp; if(rest<=0)break; } } return flow-rest;}int dinic(int s,int t){ int ans=0; for(;bfs(s,t);)ans+=dfs(s,inf,t); return ans;}int main(){ scanf("%d%d",&n,&m); S=0;T=n+1; for(int i=1;i<=n;++i){ int x;scanf("%d",&x); if(x)add(S,i,1); else add(i,T,1); } for(int i=1;i<=m;++i){ int x,y; scanf("%d%d",&x,&y); add(x,y,1);add(y,x,1); } printf("%d\n",dinic(S,T)); return 0;}