也算水题一道吧，不过Round1感性理解一下就xjb建了个图，40
Round2仔细分析了一会，理性建了个图，90
然后分析了半天……改大数组就A了……
从S到所有值为1的点连一条inf的边，从所有值为0的点向T连一条inf的边
然后对于每个值为1的点分析：
把点拆成A部和B部
改立场后自我谴责，从A部向B部连一条
改立场后本来同立场的朋友谴责，从$x_{A}$向$y_{B}$连一条
然后本来立场就不一样的朋友相信大家都会搞
然后最小割转最大流，dinic跑一下就A了
其实这题貌似不能算水题……？我也想了将近一个小时的细节……
只不过最后能被我想出来的都是水题，这个我非常确定qwq
（因为我太水了）
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 5000
#define maxm 200010
using namespace std;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} struct Edge{
int next,to,val;
}edge[maxm];
int head[maxn],num;
inline void addedge(int from,int to,int val){
edge[++num]=(Edge){head[from],to,val};
head[from]=num;
}
inline void add(int from,int to,int val){
addedge(from,to,val);
addedge(to,from,);
} inline int count(int i){ return i&?i+:i-; } bool vis[maxn];
int dfn[maxn];
int list[maxn];
int Start,End;
bool bfs(){
memset(vis,,sizeof(vis));
queue<int>q; q.push(Start); dfn[Start]=vis[Start]=;
while(!q.empty()){
int from=q.front(); q.pop();
for(int i=head[from];i;i=edge[i].next){
int to=edge[i].to;
if(vis[to]||edge[i].val==) continue;
vis[to]=; q.push(to); dfn[to]=dfn[from]+;
}
}
return vis[End];
} int dfs(int x,int val){
//printf("%d %d\n",x,val);
if(x==End||val==) return val;
int flow=; vis[x]=;
for(int i=list[x];i;i=edge[i].next){
int to=edge[i].to;
if(vis[to]||edge[i].val==||dfn[to]!=dfn[x]+) continue;
int now=dfs(to,min(val,edge[i].val));
flow+=now; edge[i].val-=now; edge[count(i)].val+=now; val-=now;
if(val<=) break;
}
if(flow!=val) dfn[x]=-;
return flow;
} int maxflow(){
int ans=;
while(bfs()){
memset(vis,,sizeof(vis));
for(int i=Start;i<=End;++i) list[i]=head[i];
int now=dfs(Start,);
if(now==) break;
ans+=now;
}
return ans;
} int q[maxn];
int qa[maxn],qb[maxn];
int n,m; int main(){
n=read(),m=read();End=maxn-;
for(int i=;i<=n;++i) q[i]=read();
for(int i=;i<=m;++i){
qa[i]=read();qb[i]=read();
}
for(int i=;i<=n;++i){
if(q[i]==){
add(Start,i,0x7fffffff);
add(i,i+n,); //拆点
add(i+n,i+n*,); //谴责自己
}
else{
add(i+n*,End,0x7fffffff);
add(i+n*,i+n*,); //拆点
add(i+n*,i+n*,); //谴责自己
}
}
for(int i=;i<=m;++i){
int x=qa[i],y=qb[i];
if(q[x]<q[y]) swap(x,y);
if(q[x]==&&q[y]==){
add(x+n,y+n*,); //互相谴责qwq
add(y+n,x+n*,);
}
else if(q[x]==&&q[y]==) add(x+n*,y+n*,);
else{
add(x+n*,y+n*,);
add(y+n*,x+n*,);
}
}
printf("%d",maxflow());
return ;
}
/*
5 5
1 0 0 1 0
1 4
1 3
2 4
3 5
4 5 6 7
1 0 1 1 0 1
1 3
1 2
1 4
3 5
3 6
4 6
4 5
*/