P2057 善意的投票 最小割理解

实现时这样建图：直接将S连向同意的人，T连向不同意的人，若两人是朋友，则在他们之间连一条双向边

    #include<bits/stdc++.h>

    #define il inline

    using namespace std;

    const int N=,inf=;

    int n,m,s,t=,h[N],cnt=,dis[N],ans;

    struct edge{

    int to,net,v;

    }e[N*];

    il void add(int u,int v,int w)

    {

        e[++cnt].to=v,e[cnt].net=h[u],e[cnt].v=w,h[u]=cnt;

        e[++cnt].to=u,e[cnt].net=h[v],e[cnt].v=,h[v]=cnt;

    }

    queue<int>q;

    il bool bfs()

    {

        memset(dis,-,sizeof(dis));

        q.push(s),dis[s]=;

        while(!q.empty())

        {

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

            for(int i=h[u];i;i=e[i].net)

            if(dis[e[i].to]==-&&e[i].v>)dis[e[i].to]=dis[u]+,q.push(e[i].to);

        }

        return dis[t]!=-;

    }

    il int dfs(int u,int op)

    {

        if(u==t)return op;

        int flow=,used=;

        for(int i=h[u];i;i=e[i].net)

        {

            int v=e[i].to;

            if(dis[v]==dis[u]+&&e[i].v>)

            {

                used=dfs(v,min(op,e[i].v));

                if(!used)continue;

                flow+=used,op-=used;

                e[i].v-=used,e[i^].v+=used;

                if(!op)break;

            }

        }

        if(!op)dis[u]=-;

        return flow;

    }

    int main()

    {

        scanf("%d%d",&n,&m);

        int x,y;

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

            scanf("%d",&x);

            if(x==)add(s,i,);

            else add(i,t,);

        }

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

            scanf("%d%d",&x,&y);

            add(x,y,),add(y,x,);

        }

        while(bfs())ans+=dfs(s,inf);

        cout<<ans;

        return ;

}