描述 Description
众所周知的 (什么? 你不知道? 去百度一下),Nobody 的团舞里有一个经典动作 (那是相当的经典, 经典了好几年), 而这个动作是对称做两遍的. 葱歌很喜欢这个动作 (Mikuer 们不要 BS 我…), 她很想多做这个动作.
但是邪恶的 F, 为了少看这无语的动作, 给了葱歌两排非负整数. 一排 A 数, 一排 B 数. A 数有 n 个, B 数有 m 个. 如果一个 A 数和一个 B 数的二进制表示法中, 每一位都不一样的话 (不足的数高位补 0), 则 A 和 B 能够组成一个 “对称音”. 每个数只能属于一个 “对称音”. 葱歌想要最多的对称音, 让她可以尽量多跳那个动作.
输入格式 InputFormat
输入共 3 行.
第 1 行两个正整数 n,m, 表示 A 数 n 个, B 数 m 个.
第 2 行 n 个非负整数, 表示 n 个 A 数.
第 3 行 m 个非负整数, 表示 m 个 B 数.
输出格式 OutputFormat
一行一个正整数, 表示最多能得到的 “对称音” 个数. 如果一个对称音都得不到, 输出 “I want nobody nobody but you”.
样例输入 SampleInput
2 1
0 1
2
样例输出 SampleOutput
1
代码 Code
二分图匹配。 一开始判断二进制是否都不同弄错了。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=405;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,nx,vl;
}e[maxn*maxn];
int head[maxn],match[maxn];
bool used[maxn];
int a[maxn],b[maxn];
int cnt=0,ans=0;
inline void ins(int u,int v)
{
e[++cnt].to=v;e[cnt].nx=head[u];
head[u]=cnt;
}
bool crosspath(int s)
{
int i,j,t,u,v,w;
for (i=head[s];i;i=e[i].nx)
{
v=e[i].to;
if (!used[v])
{
used[v]=true;
if (!match[v] || crosspath(match[v]))
{
match[v]=s;
return true;
}
}
}
return false;
}
inline void hungary()
{
int i,j,t;
for (i=1;i<=n;i++)
{
memset(used,false,sizeof(used));
if (crosspath(i)) ans++;
}
}
inline bool can(int a,int b)
{
int i,j,t;
t=a^b;
while (t>0)
{
if ((t&1)==0) return false;
t>>=1;
}
return true;
}
int main()
{
memset(match,0,sizeof(match));
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=m;i++) scanf("%d",&a[n+i]);
for (i=1;i<=n;i++) for (j=1;j<=m;j++) if (can(a[i],a[n+j])) ins(i,n+j);
hungary();
if (ans==0) printf("I want nobody nobody but you\n");
else printf("%d\n",ans);
return 0;
}