这真是一道不错的省选题，至少像我这样的蒟蒻也会写一写
首先我们发现这道题的标签是网络流，所以我们就开始考虑建图
首先我们观察性质，明显地：所有人都要么是0，要么是1。而且每个人只能是0或1
由于身经百战的独到经验，我们可以先得出以下的建图方式：
-
设超级源点S，超级汇点T。分别表示支持不睡觉和支持睡觉
-
由S向所有本意不睡觉的人连边；由所有本意睡觉的人向T连边
-
对于所有的py关系连一条双向边
-
以上所有边的流量限制均为1（冲突的代价）
我们可以发现要满足性质必须让S和T不连通
然后就成功转化为求一张图的最小割
通过最大流最小割定理知道最大流=最小割
跑最大流，Dinic即可
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int N=305,INF=1e9;
struct edge
{
int to,next,c;
}e[N*N];
int head[N],dep[N],q[N],n,m,x,y,s,t,k;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void add(int x,int y,int z)
{
e[++k].to=y; e[k].c=z; e[k].next=head[x]; head[x]=k;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline bool BFS(void)
{
memset(dep,0,sizeof(dep));
dep[s]=1; q[1]=s;
int H=0,T=1;
while (H<T)
{
int now=q[++H];
for (register int i=head[now];i!=-1;i=e[i].next)
if (!dep[e[i].to]&&e[i].c)
{
dep[e[i].to]=dep[now]+1;
q[++T]=e[i].to;
}
}
return dep[t];
}
inline int DFS(int now,int dist)
{
if (now==t) return dist;
int res=0;
for (register int i=head[now];i!=-1&&dist;i=e[i].next)
if (dep[e[i].to]==dep[now]+1&&e[i].c)
{
int dis=DFS(e[i].to,min(e[i].c,dist));
dist-=dis; res+=dis;
e[i].c-=dis; e[i^1].c+=dis;
}
if (!res) dep[now]=0;
return res;
}
inline int Dinic(void)
{
int sum=0;
while (BFS()) sum+=DFS(s,INF);
return sum;
}
int main()
{
register int i;
memset(e,-1,sizeof(e));
memset(head,-1,sizeof(head));
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
read(n); read(m); s=0; t=n+1;
for (i=1;i<=n;++i)
{
read(x);
if (x) add(i,t,1),add(t,i,0); else add(s,i,1),add(i,s,0);
}
for (i=1;i<=m;++i)
{
read(x); read(y);
add(x,y,1); add(y,x,1);
}
printf("%d",Dinic());
return 0;
}
吐槽一下网络流的题目怎么都是1A的