题意

给出一个二分图，左边为A集合，右边为B集合，要求把A集合中每一个点染为黑白两色中的一种，B集合中的颜色已定。染色后对于原本相邻且颜色相同的点，建立新的二分图，即得到了两个新的二分图，它们是独立的。求出这两个新的二分图的最大匹配数的和的最小值。数均小于等于5000。

---

 

思考

这是简化题意。由于暴力很难写，考虑网络流。将B集合中的每一个点根据其颜色分为一类和二类点。对于A集合中的每一个点，拆成两个点，两点连1的单向边，将所有相邻的一类点连线左边，另一类连向右边，值为1。所有二类点连向汇点，源点连向所有一类点。最小割。

这样，若割掉了某条边，代表了将某个点相邻的所有A集合中的点都染成了相同的颜色，并断绝了其他点的后路。

---

 

代码

1 #include
      
        2 using namespace std; 3 const int maxn=1E5+5; 4 const int inf=INT_MAX; 5 int head[maxn*2],size=1,n,m,a[maxn],dfn[maxn],S,T,x,y,ans,k; 6 struct edge{
    int to,next,w;}E[maxn*2]; 7 void add(int u,int v,int w) 8 { 9     E[++size].to=v;10     E[size].next=head[u];11     E[size].w=w;12     head[u]=size;13     14     E[++size].to=u;15     E[size].next=head[v];16     E[size].w=0;17     head[v]=size;18 }19 bool bfs()20 {21     queue
       
        Q;22     for(int i=0;i<=T;++i)dfn[i]=-1;23     dfn[S]=0;24     Q.push(S);25     while(Q.size())26     {27         int u=Q.front();28         Q.pop();29         for(int i=head[u];i;i=E[i].next)30         {31             int v=E[i].to;32             if(E[i].w==0||dfn[v]!=-1)continue;33             dfn[v]=dfn[u]+1;34             Q.push(v);35         }36     }37     return dfn[T]!=-1;38 }39 int dinic(int u,int up)40 {41     if(u==T)return up;42     int sum=0;43     for(int i=head[u];i;i=E[i].next)44     {45         int v=E[i].to;46         if(E[i].w==0||dfn[v]!=dfn[u]+1)continue;47         int g=dinic(v,min(E[i].w,up-sum));48         E[i].w-=g;49         E[i^1].w+=g;50         sum+=g;51         if(g==0)dfn[v]=-1;52         if(sum==up)break;53     }54     return sum;55 }56 int main()57 {58 //    freopen("deadline.in","r",stdin);59 //    freopen("deadline.out","w",stdout);60     ios::sync_with_stdio(false);61     cin>>n>>m>>k;62     for(int i=1;i<=n;++i)cin>>a[i];63     for(int i=1;i<=k;++i)64     {65         cin>>x>>y;66         if(a[x])add(x,y+n,inf);67         else add(y+n+m,x,inf);68     }69     S=0;70     T=n+m*2+1;71     for(int i=1;i<=m;++i)add(i+n,i+n+m,1);72     for(int i=1;i<=n;++i)73         if(a[i])add(S,i,1);74         else add(i,T,1);75     while(bfs())ans+=dinic(S,inf);76     cout<
        
         <