[Vijos1693] Miku_Nobody

描述 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


Vijos 1693


代码 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;
}