2768: [JLOI2010]冠军调查

题目连接：

Description

一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰，英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查，调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者，大家齐聚一堂，各抒己见。每一位参与者都将发言，阐述自己的看法。参与者的心里都有一个看法，比如FireDancer认为切尔西不可能夺冠，而WaterDancer认为切尔西一定问鼎。但是因为WaterDancer是FireDancer的好朋友，所以可能FireDancer为了迁就自己的好朋友，会在发言中支持切尔西。也就是说每个参与者发言时阐述的看法不一定就是心里所想的。现在告诉你大家心里的想法和参与者的朋友网，希望你能安排每个人的发言内容，使得违心说话的人的总数与发言时立场不同的朋友（对）的总数的和最小。

Input

第一行两个整数n和m，其中n（2≤n≤300）表示参与者的总数，m（0≤m≤n(n-1)/2）表示朋友的总对数。

第二行n个整数，要么是0要么是1。如果第i个整数的值是0的话，表示第i个人心里认为切尔西将与冠军无缘，如果是1的话，表示他心里认为切尔西必将夺魁。

下面m行每行两个不同的整数，i和j（1≤i, j≤n）表示i和j是朋友。注意没有一对朋友会在输入中重复出现。朋友关系是双向的，并且不会传递。

Output

只有一个整数，为最小的和

Sample Input

3 3

1 0 0

1 2

1 3

2 3

Sample Output

1

Hint

最好的安排是所有人都在发言时说切尔西不会夺冠。这样没有一对朋友的立场相左，只有第1个人他违心说了话。

题意

题解：

最小割模型

就是你要么割掉这个人，要么就割掉这个人和他朋友的边

然后跑一波最大流就好了

代码

#include
    
     using namespace std;const int MAXN=1000000,MAXM=1000000,inf=1e9;struct Edge{    int v,c,f,nx;    Edge() {}    Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}} E[MAXM];int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;void init(int _n){    N=_n,sz=0; memset(G,-1,sizeof(G[0])*N);}void link(int u,int v,int c){    E[sz]=Edge(v,c,0,G[u]); G[u]=sz++;    E[sz]=Edge(u,0,0,G[v]); G[v]=sz++;}bool bfs(int S,int T){    static int Q[MAXN]; memset(dis,-1,sizeof(dis[0])*N);    dis[S]=0; Q[0]=S;    for (int h=0,t=1,u,v,it;h
     
      E[it].f)            {                dis[v]=dis[u]+1; Q[t++]=v;            }        }    }    return dis[T]!=-1;}int dfs(int u,int T,int low){    if (u==T) return low;    int ret=0,tmp,v;    for (int &it=cur[u];~it&&ret
      
       E[it].f)        {            if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))            {                ret+=tmp; E[it].f+=tmp; E[it^1].f-=tmp;            }        }    }    if (!ret) dis[u]=-1; return ret;}int dinic(int S,int T){    int maxflow=0,tmp;    while (bfs(S,T))    {        memcpy(cur,G,sizeof(G[0])*N);        while (tmp=dfs(S,T,inf)) maxflow+=tmp;    }    return maxflow;}int main(){    init(900000);    int n,m;    scanf("%d%d",&n,&m);    int s = 0,t = n+2;    for(int i=1;i<=n;i++)    {        int x;scanf("%d",&x);        if(x)link(s,i,1);        else link(i,t,1);    }    for(int i=1;i<=m;i++)    {        int x,y;scanf("%d%d",&x,&y);        link(x,y,1);        link(y,x,1);    }    printf("%d\n",dinic(s,t));}