题目链接

bzoj 1305: [CQOI2009]dance跳舞

题解

男,女生拆点A1A2，B1B2，拆成两点间分别连容量为K的边，限制与不喜欢的人跳舞的数量

A1连接源点容量为x，B1连接汇点容量为x，x即为歌曲数目数

对与相互喜欢的男女直在A1，B1间接连容量为1的边

对于相互不喜欢A2练到B2，容量为1

二分x的大小，每次重新构图，判断该图是否满流，慢流则说明该曲目可行

代码

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 10007;

#define INF 0x7fffffff

using std::queue;

inline int read() {

    int x=0;

    char c=getchar();

    while(c<'0'||c>'9') c=getchar();

    while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();

    return x;

}

int head[maxn];

int n,m,num=0,S,T;

int bel[maxn];

struct node{

    int v,next,flow;

}edge[maxn<<4];

void add_edge(int u,int v,int flow) {

    edge[++num].v=v;edge[num].flow=flow;edge[num].next=head[u];head[u]=num;

    edge[++num].v=u;edge[num].flow=0;edge[num].next=head[v];head[v]=num;

}

int cur[maxn],lev[maxn];

bool bfs() {

    memset(lev,-1,sizeof lev);

    memcpy(cur,head,sizeof head);

    queue<int>que;

    que.push(S);lev[S]=0;

    while(!que.empty()) {

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

        for(int i=head[u];i;i=edge[i].next) {

            int v=edge[i].v;

            if(edge[i].flow>0&&lev[v]<0) {

                lev[v]=lev[u]+1;que.push(v);

            }

        }

    }

    if(lev[T]!=-1)return true;

    else return false;

}

int dfs(int now,int flow) {

    if(now==T)return flow;

    int rest=0,delta;

    for(int &i=cur[now];i;i=edge[i].next) {

        int v=edge[i].v;

        if(lev[v]==lev[now]+1&&edge[i].flow>0) {

            delta=dfs(v,min(flow-rest,edge[i].flow));

            if(delta) {

                edge[i].flow-=delta;

                edge[i^1].flow+=delta;

                rest+=delta;if(rest==flow)break;

            }

        }

    }

    if(rest==flow)lev[now]=-1;

    return rest;

}

int dinic() {

    int ans=0;

    while(bfs())

         ans+=dfs(S,INF);

    return ans;

}

int main() {

    n=read(),m=read();

    T=n+1;

    for(int p,i=1;i<=n;++i) {

        p=read();

        if(p==1)add_edge(S,i,1),bel[i];

        else add_edge(i,T,1);

    }

    for(int a,b,i=1;i<=m;++i) {

        a=read(),b=read();

        add_edge(a,b,2);

        add_edge(b,a,2);

    }

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

    return 0;

}