BZOJ 2768チャンピオン調査(最小割)

タイトルリンク:http://61.187.179.132/JudgeOnline/problem.php?id=2768
題意:無方向図を与え、各点に0または1の値がある.各ポイントの値0または1を再設定します.再設定後の点と元の点がx個ある点の値が異なるとする.再設定後、uとvの値が異なるようにy辺(u,v)があります.x+yを最小化します.
考え方:初期値が1の場合、原点はその辺に接続されます.そうでなければ、そのポイントはエッジに接続されます.エッジ(u,v)について、uとvの値が異なると、エッジが接続されます.最小割を求める.左側が切り取られると、それを0に変更することを示す.右側が切られると、それを1に変更することを示します.中間が切られると両側の衝突を表す.
 

struct node

{

    int v,cap,next;

};









node edges[N];

int head[N],e;









void add(int u,int v,int cap)

{

    edges[e].v=v;

    edges[e].cap=cap;

    edges[e].next=head[u];

    head[u]=e++;

}









void Add(int u,int v,int cap)

{

    add(u,v,cap);

    add(v,u,0);

}









int pre[N],h[N],num[N],cur[N];









int Maxflow(int s,int t,int n)

{

    int i;

    for(i=0;i<=n;i++) h[i]=num[i]=0,cur[i]=head[i];

    int ans=0,u=s,v,x,Min;

    

    while(h[u]<n)

    {

        if(u==t)

        {

            Min=INF+1;

            for(i=s;i!=t;i=edges[cur[i]].v)

            {

                x=cur[i];

                if(edges[x].cap<Min) Min=edges[x].cap,v=i;

            }

            ans+=Min; u=v;

            for(i=s;i!=t;i=edges[cur[i]].v)

            {

                x=cur[i];

                edges[x].cap-=Min;

                edges[x^1].cap+=Min;

            }

        }

        for(i=cur[u];i!=-1;i=edges[i].next)

        {

            v=edges[i].v;

            if(edges[i].cap>0&&h[u]==h[v]+1) break;

        }

        if(i!=-1)

        {

            cur[u]=i;

            pre[edges[i].v]=u;

            u=edges[i].v;

        }

        else

        {

            if(--num[h[u]]==0) break;

            cur[u]=head[u];

            x=n;

            for(i=head[u];i!=-1;i=edges[i].next)

            {

                if(edges[i].cap>0) x=min(x,h[edges[i].v]);

            }

            h[u]=x+1;

            num[x+1]++;

            if(u!=s) u=pre[u];

        }

    }

    return ans;

}









int s,t,n,m,a[N];

















int main()

{

    clr(head,-1);

    RD(n,m);

    s=0; t=n+1;

    int i,x,y;

    FOR1(i,n) 

    {

        RD(a[i]);

        if(a[i]) Add(s,i,1);

        else Add(i,t,1);

    }

    FOR1(i,m)

    {

        RD(x,y);

        if(a[x]==a[y]) continue;

        if(a[x]) Add(x,y,1);

        else Add(y,x,1);

    }

    PR(Maxflow(s,t,t+1));

}