19_04_02校内训练[deadline]

题意

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

---

思考

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

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

---

代码

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=1E5+;

 const int inf=INT_MAX;

 int head[maxn*],size=,n,m,a[maxn],dfn[maxn],S,T,x,y,ans,k;

 struct edge{int to,next,w;}E[maxn*];

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

 {

     E[++size].to=v;

     E[size].next=head[u];

     E[size].w=w;

     head[u]=size;

     E[++size].to=u;

     E[size].next=head[v];

     E[size].w=;

     head[v]=size;

 }

 bool bfs()

 {

     queue<int>Q;

     for(int i=;i<=T;++i)dfn[i]=-;

     dfn[S]=;

     Q.push(S);

     while(Q.size())

     {

         int u=Q.front();

         Q.pop();

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

         {

             int v=E[i].to;

             if(E[i].w==||dfn[v]!=-)continue;

             dfn[v]=dfn[u]+;

             Q.push(v);

         }

     }

     return dfn[T]!=-;

 }

 int dinic(int u,int up)

 {

     if(u==T)return up;

     int sum=;

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

     {

         int v=E[i].to;

         if(E[i].w==||dfn[v]!=dfn[u]+)continue;

         int g=dinic(v,min(E[i].w,up-sum));

         E[i].w-=g;

         E[i^].w+=g;

         sum+=g;

         if(g==)dfn[v]=-;

         if(sum==up)break;

     }

     return sum;

 }

 int main()

 {

 //    freopen("deadline.in","r",stdin);

 //    freopen("deadline.out","w",stdout);

     ios::sync_with_stdio(false);

     cin>>n>>m>>k;

     for(int i=;i<=n;++i)cin>>a[i];

     for(int i=;i<=k;++i)

     {

         cin>>x>>y;

         if(a[x])add(x,y+n,inf);

         else add(y+n+m,x,inf);

     }

     S=;

     T=n+m*+;

     for(int i=;i<=m;++i)add(i+n,i+n+m,);

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

         if(a[i])add(S,i,);

         else add(i,T,);

     while(bfs())ans+=dinic(S,inf);

     cout<<ans<<endl;

     return ;

 }