网络流/最小割
我不会告诉你这题跟 BZOJ 1934 是一模一样的……包括数据范围……
/**************************************************************
Problem: 2768
User: Tunix
Language: C++
Result: Accepted
Time:32 ms
Memory:4408 kb
****************************************************************/ //BZOJ 2768
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,M=,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int n,m;
struct edge{
int from,to,v;
};
inline int pack(int i,int j){return (i-)*m+j;}
struct Net{
edge E[M];
int head[N],next[M],cnt;
void add(int x,int y,int v){
E[++cnt]=(edge){x,y,v};
next[cnt]=head[x]; head[x]=cnt;
E[++cnt]=(edge){y,x,};
next[cnt]=head[y]; head[y]=cnt;
}
int s,t,cur[N],d[N],Q[N];
void init(){
n=getint();m=getint();
cnt=;
s=; t=n+;
F(i,,n)
if (getint()) add(s,i,);
else add(i,t,);
int x,y;
F(i,,m){
x=getint(); y=getint();
add(x,y,);
add(y,x,);
}
}
bool mklevel(){
memset(d,-,sizeof d);
d[s]=;
int l=,r=-;
Q[++r]=s;
while(l<=r){
int x=Q[l++];
for(int i=head[x];i;i=next[i])
if (d[E[i].to]==- && E[i].v){
d[E[i].to]=d[x]+;
Q[++r]=E[i].to;
}
}
return d[t]!=-;
}
int dfs(int x,int a){
if (x==t||a==) return a;
int flow=;
for(int &i=cur[x];i && flow<a;i=next[i])
if (d[E[i].to]==d[x]+ && E[i].v){
int f=dfs(E[i].to,min(a-flow,E[i].v));
E[i].v-=f;
E[i^].v+=f;
flow+=f;
}
if (!flow) d[x]=-;
return flow;
}
int Dinic(){
int flow=;
while(mklevel()){
F(i,s,t) cur[i]=head[i];
flow+=dfs(s,INF);
}
return flow;
}
}G1;
int main(){
#ifndef ONLINE_JUDGE
freopen("2768.in","r",stdin);
freopen("2768.out","w",stdout);
#endif
G1.init();
printf("%d\n",G1.Dinic());
return ;
}