BZOJ2744 HEOI2012朋友圈(二分图匹配)

  先考虑B国。容易发现a xor b mod 2=0即二进制末位相同,那么可以据此将所有人分成两部分,每一部分各自是一个完全图。然后再将a or b有奇数个1的边连上,现在需要求的就是这样一个图里的最大团。我们知道最大团=反图最大独立集,这个图的反图显然是一个二分图,那么跑二分图匹配就可以求出这个了。

  A国同样根据二进制末位分成两部分。显然不可能选择末位相同的两人。于是暴力枚举在A国选择哪些人,只留下B国与其有边的人跑匹配就可以了。

  不管复杂度。

  在一些非常弱智的地方wa了好长时间,没救。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 3010
int n,m,k,a[N],b[N],p[N],q[N],tag[N],match[N],t,ans,tot,cnt;
bool flag[N][N],f[N][N];
struct data{int to,nxt;
}edge[N*N];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
bool hungary(int k,int from)
{
for (int i=p[k];i;i=edge[i].nxt)
if (tag[edge[i].to]!=from)
{
tag[edge[i].to]=from;
if (!match[edge[i].to]||hungary(match[edge[i].to],from))
{
match[edge[i].to]=k;
return ;
}
}
return ;
}
void pre()
{
memset(p,,m+<<);
memset(match,,m+<<);
memset(tag,,m+<<);
tot=;t=;cnt=;
}
void solve()
{
for (int j=;j<=cnt;j++)
for (int k=;k<=cnt;k++)
if (f[q[j]][q[k]]) addedge(q[j],q[k]);
for (int j=;j<=cnt;j++)
if (b[q[j]]&) tot+=hungary(q[j],q[j]);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj2744.in","r",stdin);
freopen("bzoj2744.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read(),k=read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<=m;i++) b[i]=read();
for (int i=;i<=k;i++)
{
int x=read(),y=read();
flag[x][y]=;
}
for (int i=;i<=m;i++)
for (int j=;j<=m;j++)
if ((b[i]&)&&!(b[j]&))
{
int x=b[i]|b[j],y=;
while (x) y^=,x-=x&-x;
if (!y) f[i][j]=,addedge(i,j);
}
for (int i=;i<=m;i++)
if (b[i]&) tot+=hungary(i,i);
ans=m-tot;
for (int i=;i<=n;i++)
{
pre();
for (int j=;j<=m;j++)
if (flag[i][j]) q[++cnt]=j;
solve();
ans=max(ans,cnt-tot+);
}
for (int x=;x<n;x++)
for (int y=x+;y<=n;y++)
if ((a[x]^a[y])&)
{
pre();
for (int j=;j<=m;j++)
if (flag[x][j]&&flag[y][j]) q[++cnt]=j;
solve();
ans=max(ans,cnt-tot+);
}
cout<<ans;
return ;
}
上一篇:Stats 20 Lec 2: Sample Final Exam


下一篇:Hadoop系列002-从Hadoop框架讨论大数据生态