bzoj 2744 朋友圈

题目大意：

两个国家各有A和B个人，每个人有一个数值。

若两个A国的人满足$val_i\space xor \space val_j \mod 2 =1$ 则他们为朋友

若两个B国的人满足$val_i\space xor \space val_j \mod 2 =0$或者二进制下$val_i \space or\space val_j$中有奇数个1 则他们为朋友

给出一些A国的人与B国的人的朋友关系

求图的最大团

思路：

直接求最大团并不好求，发现A国的人最多取2个

而B国形成的图的反图一定为二分图（奇偶相连），而二分图反图的最大团=最大点独立集=$n-$最大匹配

因此我们先建出B国的反图，枚举选A国的人的情况，对每种情况在图上打$tag$ 跑$Dinic$即可

（完全忘记匈牙利.jpg

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<map>

 #include<set>

 #define ll long long

 #define db double

 #define inf 2139062143

 #define MAXN 3010

 #define MAXM 5001000

 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)

 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)

 #define ren for(register int i=fst[x];i;i=nxt[i])

 #define pb(i,x) vec[i].push_back(x)

 #define pls(a,b) (a+b)%MOD

 #define mns(a,b) (a-b+MOD)%MOD

 #define mul(a,b) (1LL*(a)*(b))%MOD

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int na,nb,m,ans,S,T,a[],b[MAXN],t1,t2;vector<int> vec[];

 struct Dinic

 {

     int S,T,fst[MAXN],nxt[MAXM<<],to[MAXM<<],val[MAXM<<],cnt,cur[MAXN];

     int vis[MAXN],dis[MAXN],tot,q[MAXN],l,r,o1[MAXN],o2[MAXN];

     Dinic(){memset(fst,,sizeof(fst));cnt=;}

     void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}

     void ins(int u,int v,int w) {add(u,v,w);add(v,u,);}

     int bfs()

     {

         q[l=r=]=T,vis[T]=++tot,dis[T]=;int x;

         while(l<=r)

         {

             x=q[l++];ren if(o1[to[i]]==t1&&o2[to[i]]==t2&&vis[to[i]]!=tot&&val[i^])

                 dis[to[i]]=dis[x]+,vis[to[i]]=tot,q[++r]=to[i];

         }

         return vis[S]==tot;

     }

     int dfs(int x,int a)

     {

         if(x==T||!a) return a;int flw=,f;

         for(int& i=cur[x];i&&a;i=nxt[i])

             if(dis[to[i]]==dis[x]-&&val[i]&&(f=dfs(to[i],min(a,val[i]))))

                 a-=f,flw+=f,val[i]-=f,val[i^]+=f;

         return flw;

     }

     int solve(int _s,int _t,int res=)

     {

         S=_s,T=_t;int f;while(bfs())

             {rep(i,,max(S,T)) cur[i]=fst[i];while(f=dfs(S,inf)) res+=f;}

         return res;

     }

 }D;

 int lowbit(int x) {return x&(-x);}

 int cheq(int x,int res=) {for(;x;x-=lowbit(x)) res++;return !(res&);}

 int vis[MAXN],vis2[MAXN];

 int main()

 {

     na=read(),nb=read(),m=read();int x,y,sum;S=nb+,T=S+;

     rep(i,,na) a[i]=read();rep(i,,nb) b[i]=read();

     while(m--) x=read(),y=read(),pb(x,y);

     rep(i,,nb) if(b[i]&) D.ins(S,i,);

         else {D.ins(i,T,);rep(j,,nb) if((b[j]&)&&cheq(b[i]|b[j])) D.ins(j,i,);}

     rep(i,,na) pb(i,S),pb(i,T);

     ans=max(ans,nb-D.solve(S,T));D.solve(T,S);

     rep(i,,na)

     {

         sum=-;rep(x,,vec[i].size()-) D.o1[vec[i][x]]=i,sum++;

         t1=i,ans=max(ans,sum+-D.solve(S,T));D.solve(T,S);

     }

     rep(i,,na) if(a[i]&)

     {

         rep(x,,vec[i].size()-) D.o1[vec[i][x]]=i+na;t1=i+na,sum=-;

         rep(j,i+,na) if(!(a[j]&))

         {

             rep(x,,vec[j].size()-) D.o2[vec[j][x]]=i*na+j,sum+=(D.o1[vec[j][x]]==t1);

             t2=i*na+j;ans=max(ans,sum+-D.solve(S,T));D.solve(T,S);sum=-;

         }

     }

     printf("%d",ans);

 }

巴特西

bzoj 2744 朋友圈

最新文章

热门文章