#include<cstdio>
#include<iostream>
#define M 100000
#include<cstring>
using namespace std;
int cnt=,head[M],next[*M],u[*M],v[*M],n,m,d[M],q[M],ans;
void jia(int a1,int a2,int a3)
{
cnt++;
u[cnt]=a2;
v[cnt]=a3;
next[cnt]=head[a1];
head[a1]=cnt;
return;
}
bool bfs()
{
memset(d,,sizeof(int)*(n+));
int h=,t=;
q[]=;
d[]=;
for(;h<t;)
{
h++;
int p=q[h];
for(int i=head[p];i;i=next[i])
if(!d[u[i]]&&v[i])
{
d[u[i]]=d[p]+;
if(d[n])
return ;
t++;
q[t]=u[i];
}
}
return ;
}
int dinic(int s,int f)
{
if(s==n)
return f;
int rest=f;
for(int i=head[s];i&&rest;i=next[i])
if(v[i]&&d[u[i]]==d[s]+)
{
int now=dinic(u[i],min(rest,v[i]));
if(!now)
d[u[i]]=;
v[i]-=now;
v[i^]+=now;
rest-=now;
}
return f-rest;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
int a1;
scanf("%d",&a1);
if(a1)
{
jia(,i,);
jia(i,,);
}
else
{
jia(i,n+,);
jia(n+,i,);
}
}
for(int i=;i<=m;i++)
{
int a1,a2;
scanf("%d%d",&a1,&a2);
jia(a1,a2,);
jia(a2,a1,);
jia(a2,a1,);
jia(a1,a2,);
}
n++;
for(;bfs();)
ans+=dinic(,0x7fffffff);
printf("%d\n",ans);
return ;
}
网络流最小割 将源点与睡觉的相连，不睡觉的与汇点相连。朋友之间相连，跑最小割既是答案。