传送门
Solution
比较巧妙啊！
考虑这个只有同意和不统一两种，所以直接令\(s\)表示选，\(t\)表示不选，然后在朋友直接建双向边就好了。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=500010,Inf=1e9+10;
int front[N],cnt,s,t,n,m;
struct node
{
int to,nxt,w;
}e[1500010];
queue<int>Q;
int dep[N];
inline int gi()
{
int sum=0,f=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
void Add(int u,int v,int w)
{
e[cnt]=(node){v,front[u],w};front[u]=cnt++;
e[cnt]=(node){u,front[v],0};front[v]=cnt++;
}
bool bfs()
{
memset(dep,0,sizeof(dep));
Q.push(s);dep[s]=1;
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=front[u];i!=-1;i=e[i].nxt)
{
int v=e[i].to;
if(!dep[v] && e[i].w)
{
dep[v]=dep[u]+1;Q.push(v);
}
}
}
return dep[t];
}
int dfs(int u,int flow)
{
if(u==t || !flow)return flow;
for(int i=front[u];i!=-1;i=e[i].nxt)
{
int v=e[i].to;
if(dep[v]==dep[u]+1 && e[i].w)
{
int di=dfs(v,min(flow,e[i].w));
if(di)
{
e[i].w-=di;e[i^1].w+=di;
return di;
}
else dep[v]=0;
}
}
return 0;
}
int dinic()
{
int flow=0;
while(bfs())
{
while(int d=dfs(s,Inf))flow+=d;
}
return flow;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
#endif
memset(front,-1,sizeof(front));
n=gi();m=gi();t=n+1;
for(int i=1;i<=n;i++)
{
int x=gi();
if(x)Add(s,i,1);
else Add(i,t,1);
}
while(m--)
{
int u=gi(),v=gi();
Add(u,v,1);Add(v,u,1);
}
printf("%d\n",dinic());
return 0;
}