Eva

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 2980  Solved: 1904
Description

幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。 我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？

第一行只有两个整数n，m，保证有2≤n≤300，1≤m≤n(n-1)/2。其中n代表总人数，m代表好朋友的对数。文件第二行有n个整数，第i个整数代表第i个小朋友的意愿，当它为1时表示同意睡觉，当它为0时表示反对睡觉。接下来文件还有m行，每行有两个整数i，j。表示i，j是一对好朋友，我们保证任何两对i，j不会重复。

只需要输出一个整数，即可能的最小冲突数。

3 3
1 0 0
1 2
1 3
3 2

1

在第一个例子中，所有小朋友都投赞成票就能得到最优解

/**************************************************************

    Problem: 1934

    User: ictsing

    Language: C++

    Result: Accepted

    Time:16 ms

    Memory:5984 kb

****************************************************************/

 

//BZOJ1934 [Shoi2007]Vote 善意的投票

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

int n,s,t;

int ans=0;

int ecnt=1;

const int inf = 1e9;

const int mt = 300+5;

int adj[mt],cur[mt],lev[mt];

const int mm = 100000;

int to[mm<<2],nxt[mm<<2],cap[mm<<2];

queue<int>q;

void adde(int u,int v,int c)

{

    ecnt++,to[ecnt]=v,cap[ecnt]=c,nxt[ecnt]=adj[u],adj[u]=ecnt;

    ecnt++,to[ecnt]=u,cap[ecnt]=0,nxt[ecnt]=adj[v],adj[v]=ecnt;

}

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

bool bfs()

{

    while(!q.empty()) q.pop();

    memset(lev,-1,sizeof(lev));

    for(int i=1;i<=t;i++) cur[i]=adj[i];

    lev[s]=0,q.push(s);

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(int i=adj[u];i;i=nxt[i])

        {

            int v=to[i];

            if(lev[v]==-1&&cap[i])

            {

                lev[v]=lev[u]+1;

                q.push(v);

                if(v==t) return true;

            }

        }

    }

    return false;

}

int dfs(int u,int flow)

{

    if(u==t) return flow;

    int delta,res=0;

    for(int &i=cur[u];i;i=nxt[i])

    {

        int v=to[i];

        if(cap[i]&&lev[v]==lev[u]+1)

        {

            delta=dfs(v,min(cap[i],flow-res));

            cap[i]-=delta,cap[i^1]+=delta,res+=delta;

            if(res==flow) return flow;

        }

    }

    if(res<flow) lev[u]=-1;

    return res;

}

void mincut()

{

    while(bfs())

        ans+=dfs(s,inf);

}

int main()

{

    n=read();int m=read();

    s=n+1,t=s+1;

    for(int i=1;i<=n;i++)

    {

        int x=read();

        if(x) adde(s,i,1);

        else adde(i,t,1);

    }

    for(int i=1;i<=m;i++)

    {

        int x=read(),y=read();

        adde(x,y,1);

        adde(y,x,1);

    }

    mincut();

    printf("%d\n",ans);

    return 0;

}