题目：
小Z在机房。他和其它机房同学都面临一个艰难的抉择，那就是 要不要划水？
每个人都有自己的一个意见，有的人想做题，有的人想划水。
当然，每个人只能选择一个事情做。如果一个人做的事情和他想做的不同，那么他会产生1不满意度。
更棘手的是，他们之间一些人是朋友，如果两人是朋友，但是他们做的事情不同，那么会有1不满意度产生。
小Z不想看到大家闹得不高兴，他想知道，不满意度最小能是多少？
输入/输出格式
第一行两个数字n,m 分别表示有n个人和m对朋友关系
第二行n个0/1，1表示想做题，0表示想划水。
然后是m行，每行两个数字a,b 表示a和b是朋友
输出只包含一个数字，表示最小的不满意度。
样例输入/输出
Input:
3 1
0 1 0
1 2
Output:
1
样例解释
每个人都做自己想做的事情，但是1和2不同，所以答案是1.
还有答案是1的其它方案，可以证明这是最小的不满意度。
数据范围与约定
对于10%的数据，满足n<=10 m=10
对于30%的数据，满足n,m<=20
对于100%的数据，满足n<=300 m<=n*(n-1)/2
保证没有重复的朋友关系。
这题。。。网络流。。
根据最小割=最大流
网络流就是正解。。
那么怎么建图呢？
如果一个人想读书，那么从S到i连一条流量为1的边
否者从i到T连一条流量为1的边
如果有2个人是朋友。那么他们互相连一条流量为1的边。
很显然，如果2个朋友的选项不同，那么就会产生一条由S到T的通路。
那么我们求这道题的最小割即为本题答案
下面贴代码
#include<cstdio> #include<cstring> #include<algorithm> #define r register #define inf 0x3f3f3f3f using namespace std; int n,m,num=1; int S,T; struct edge{ int next,to,w; }g[100050]; int que[305]; int head[305]; int lev[305]; int iter[305]; void ins(int u,int v,int w){g[++num].next=head[u];g[num].to=v;head[u]=num;g[num].w=w;} void insw(int u,int v,int w){ins(u,v,w);ins(v,u,0);} bool bfs(){ memset(lev,-1,sizeof(lev)); lev[S]=0; int h=1,t=1; que[h]=S; while(h<=t) { int tmp=que[h]; for(int i=head[tmp];i;i=g[i].next) { if(lev[g[i].to]==-1&&g[i].w) { que[++t]=g[i].to; lev[g[i].to]=lev[tmp]+1; } } h++; } return lev[T]!=-1; } int dfs(int u,int v,int flow) { if(u==v) return flow; r int used=0; for(r int i=head[u];i;i=g[i].next) { if(g[i].w&&lev[g[i].to]==lev[u]+1) { r int fl=dfs(g[i].to,v,min(flow-used,g[i].w)); used+=fl;g[i].w-=fl;g[i^1].w+=fl; if(used==flow) return flow; } } if(!used)lev[u]=-1; return used; } int dinic() { r int flow=0; while(bfs()) { r int fl=dfs(S,T,inf); while(fl)flow+=fl,fl=dfs(S,T,inf); } return flow; } int main(){ freopen("boat.in","r",stdin); freopen("boat.out","w",stdout); scanf("%d%d",&n,&m); S=0;T=n+1; r int x,y; for(r int i=1;i<=n;i++){scanf("%d",&x);if(x)insw(S,i,1); else insw(i,T,1);} for(r int i=1;i<=m;i++){scanf("%d%d",&x,&y);ins(x,y,1);ins(y,x,1);} printf("%d",dinic()); return 0; fclose(stdin); fclose(stdout); }