又是一道玄学的网络流题
我们这样建图：
对于同意观点1的原点向其连边，对于同一观点2点向汇点连边
然后如果两个人是朋友，就连一条双向边。
为什么这样是对的呢？
对于一个人来说，他要么放弃自己的观点，就是断掉自己和原点或汇点的边
或者说他放弃他的朋友（太表面了）断掉和他朋友相连的边
最后要使原点和汇点不连通（因为一个人不可能同意两个观点），所以我们要求的就是一个最小割
跑最大流的板子就好了
# include<iostream>
# include<cstdio>
# include<algorithm>
# include<cstring>
# include<cmath>
# include<queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int mn = ;
int head[mn],edge_max=;
struct edge{int to,next,flow;
};
edge e[mn*mn*];
int n,m;
void add_edge(int x,int y,int z)
{
e[++edge_max].to=y;
e[edge_max].next=head[x];
e[edge_max].flow=z;
head[x]=edge_max;
}
void add(int x,int y,int z)
{
add_edge(x,y,z);
add_edge(y,x,);
}
queue<int> q;
int deep[mn];
bool bfs(int x,int y)
{
memset(deep,,sizeof(deep));
q.push(x);
deep[x]=;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next)
{
if(e[i].flow> && deep[e[i].to]==)
{
deep[e[i].to]=deep[u]+;
q.push(e[i].to);
}
}
}
return deep[y]!=;
}
int dfs(int x,int cost,int y)
{
if(x==y) return cost;
for(int i=head[x];i;i=e[i].next)
{
if(deep[e[i].to]==deep[x]+ && e[i].flow>)
{
int di=dfs(e[i].to,min(cost,e[i].flow),y);
if(di>)
{
e[i].flow-=di;
e[i^].flow+=di;
return di;
}
}
}
return ;
}
int dinic(int x,int y)
{
int ans=;
while(bfs(x,y))
{
// printf("ssss\n");
while(int k=dfs(x,inf,y))
ans+=k;
// printf("%d\n",ans);
}
return ans;
}
int main()
{
int st,en,x,y;
scanf("%d%d",&n,&m);
st=n+,en=n+;
for(int i=;i<=n;i++)
{
scanf("%d",&x);
if(x) {
add(st,i,);
//printf("%d %d\n",st,i);
}
else add(i,en,);
}
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y,),add(y,x,);
}
printf("%d",dinic(st,en));
return ;
}