题目大意:题面讲的这么清晰明白
具体思路:最小割:
建立超级源汇点，希望切尔西赢的从S向它连容量为1的边，希望切尔西输的从它向T连容量为1的边。在朋友之间连一条双向边，答案就是最小割。
如果存在一条从S到T的路径，相当于产生了冲突。必须说谎（割掉到S或T的边）或者与朋友意见不统一（割掉和朋友的边）
AC代码
#include<bits/stdc++.h> #define INF 100000000 using namespace std; int n,m,i,j,S,T,top=1,x,y; int a[200000],first[200000],cur[200000],last[200000],f[200000],next[200000],to[200000],cap[200000]; queue<int> q; bool bo[200000]; void add(int x,int y,int z) { top++,to[top]=y,cap[top]=z; if(first[x]==0)first[x]=top;else next[last[x]]=top; last[x]=top; } bool BFS() { while(!q.empty())q.pop(); for(i=1;i<=n+2;i++)f[i]=INF,bo[i]=false; f[S]=0;q.push(S);bo[S]=true; while(!q.empty()) { int now=q.front();q.pop();bo[now]=false; for(int i=first[now];i;i=next[i]) if(f[to[i]]>f[now]+1&&cap[i]) { f[to[i]]=f[now]+1; if(!bo[to[i]])q.push(to[i]),bo[to[i]]=true; } } if(f[T]!=INF)return true;else return false; } int DFS(int now,int flow) { if(flow==0)return 0; if(now==T)return flow; int tot=0; for(int i=cur[now];i;i=next[i],cur[now]=i) if(f[now]+1==f[to[i]]&&cap[i]&&flow) { int del=DFS(to[i],min(flow,cap[i])); tot+=del;flow-=del,cap[i]-=del,cap[i^1]+=del; } return tot; } int main() { scanf("%d%d",&n,&m); S=n+1,T=n+2; for(i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i])add(S,i,1),add(i,S,0);else add(T,i,0),add(i,T,1); } for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(a[x]==a[y])add(x,y,1),add(y,x,1); else { if(a[x])add(x,y,1),add(y,x,0);else add(y,x,1),add(x,y,0); } } int ans=0; while(BFS()) { for(i=1;i<=n+2;i++)cur[i]=first[i]; ans+=DFS(S,INF); } printf("%d",ans); return 0; }