P1402酒店之王

考虑到问题

能使最多顾客满意呢

所以我们应以客人为主要限制目标，所以将其放中间，两边各连房间和菜，于是便可转化为最大流问题

建图应注意到客人只要一个，所以对每个客人应建两点，相连的权值为1，左边点与房间相连，右边点与菜相连

const int N = 2e5 + 86;

struct egdes
{
    int to, nxt, w;
} e[N * 2];
int hd[N * 2], cur[N * 2], tot = 1, st, en;
vi lv;
void add(int x, int y, int w)
{
    e[++tot] = (egdes){y, hd[x], w};
    hd[x] = tot;
}

int bfs()
{
    lv.assign(N, 0);
    memcpy(cur, hd, sizeof(hd));
    queue<int> q;
    q.push(st);
    lv[st] = 1;
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int eg = hd[p]; eg; eg = e[eg].nxt)
        {
            int to = e[eg].to, vol = e[eg].w;
            if (vol && !lv[to])
            {
                lv[to] = lv[p] + 1;
                q.push(to);
            }
        }
    }
    return lv[en];
}

int dfs(int ss, int flow)
{
    if (ss == en)
        return flow;
    int r = flow;
    for (int eg = cur[ss]; eg && r; eg = e[eg].nxt)
    {
        cur[ss] = eg;
        int to = e[eg].to, vol = e[eg].w;
        if (vol && lv[to] == lv[ss] + 1)
        {
            int c = dfs(to, min(r, vol));
            r -= c;
            e[eg].w -= c;
            e[eg ^ 1].w += c;
        }
    }
    return flow - r;
}
int rs, fj, cai;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> rs>>fj>>cai;
    st=rs+fj+cai+4,en=st+1;
    f(i,1,cai){
        add(st,i,1);
        add(i,st,0);
    }
    f(i,1,fj){
        add(rs+cai+i,en,1);
        add(en,rs+cai+i,0);
    }
    f(i,1,rs){
        add(cai+i,en+i,1);
        add(en+i,cai+i,0);
    }
    f(i, 1, rs)
    {
        f(j, 1, fj)
        {
            int x;
            cin >> x;
            if (x)
            {
                add(en+i,cai+rs+j,1);
                add(cai+rs+j,en+i,0);
            }
        }
    }
    f(i, 1,rs)
    {
        f(j, 1, cai)
        {
            int x;
            cin >> x;
            if (x)
            {
                add(j,cai+i,1);
                add(cai+i,j,0);
            }
        }
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(st,3e8);
    }
    cout<<ans;
    return 0;
}