2010-1124

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

Doraemon和Nobita出problem，每个problem由若干idea构成，若有两道题的idea重复数量超过一个限定并且这两道题分别来自Doraemon和Nobita，那么这两个problem算作重复，不能同时出现。
现在给定两个人的problem和每个problem的idea，求做多有几个problem

首先将所有problem放在一个集合里，然后去重，因为只有分别来自两个人的才可能重复，所以相当于求最大匹配数
由于idea可能达到1024，共有2^1024^-1种状态，所以进行状态压缩，将1024位分为32×32来存储每个problem的状态

代码如下：
{{{
#!python
#include <cstdio>
#include <memory.h>

using namespace std;

const int MaxN = 1001;
const int MaxL = 32;

bool graph[MaxN][MaxN];
bool visit[MaxN];
int match[MaxN];
int f[1<<16];
unsigned int D_idea[MaxN][MaxL];
unsigned int N_idea[MaxN][MaxL];
int n;
int m;
int t;
int l;

#define debug 0

void init(void)
{
    int n;
    int k;

    for (n=0; n<1<<16; ++n)
    {
        int temp = n;
        int sum(0);
        while (temp != 0)
        {
            sum += temp % 2;
            temp /= 2;
        }
        f[n] = sum;
    }

    return;
}

bool dfs(int k)
{
    int i;
    int temp;

    for (i=0; i<m; ++i)
    {
        if (graph[k][i] && !visit[i])
        {
            visit[i] = true;
            temp = match[i];

            if (temp == -1 || dfs(temp))
            {
                match[i] = k;
                return true;
            }
        }
    }

    return false;
}

int main(void)
{
    int i;
    int j;
    int k;
    int num;
    int id;

    init();

#if debug
    freopen("in.txt", "r", stdin);
#endif
    while (scanf("%d %d %d %d", &n, &m, &t, &l) != EOF)
    {
        memset(N_idea, 0, sizeof(N_idea));
        memset(D_idea, 0, sizeof(D_idea));
        memset(graph, false, sizeof(graph));
        for (i=0; i<n; ++i)
        {
            scanf("%d", &num);
            for (j=0; j<num; ++j)
            {
                scanf("%d", &id);
                --id;
                D_idea[i][id/32] += 1u << (id % 32);
            }
        }
        for (i=0; i<m; ++i)
        {
            scanf("%d", &num);
            for (j=0; j<num; ++j)
            {
                scanf("%d", &id);
                --id;
                N_idea[i][id/32] += 1u << (id % 32);
            }
        }
        //initial graph
        for (i=0; i<n; ++i)
        {
            for (j=0; j<m; ++j)
            {
                num = 0;
                for (k=0; k<MaxL; ++k)
                {
                    unsigned int temp = D_idea[i][k] & N_idea[j][k];
                    num += f[temp >> 16] + f[temp & 0x0000ffff];
                }
                if (num >= l)
                {
                    graph[i][j] = true;
                }
            }
        }

        num = 0;
        memset(match, -1, sizeof(match));
        for (i=0; i<n; ++i)
        {
            memset(visit, false, sizeof(visit));

            if (dfs(i))
            {
                ++num;
            }
        }

        printf("%d\n", n + m - num);
    }

    return 0;
}
}}}
[by delta_4d]

Doraemon和Nobita出problem，每个problem由若干idea构成，若有两道题的idea重复数量超过一个限定并且这两道题分别来自Doraemon和Nobita，那么这两个problem算作重复，不能同时出现。

现在给定两个人的problem和每个problem的idea，求做多有几个problem

首先将所有problem放在一个集合里，然后去重，因为只有分别来自两个人的才可能重复，所以相当于求最大匹配数

由于idea可能达到1024，共有2¹⁰²⁴-1种状态，所以进行状态压缩，将1024位分为32×32来存储每个problem的状态

代码如下：

#include <cstdio>
#include <memory.h>
using namespace std;
const int MaxN = 1001;
const int MaxL = 32;
bool graph[MaxN][MaxN];
bool visit[MaxN];
int match[MaxN];
int f[1<<16];
unsigned int D_idea[MaxN][MaxL];
unsigned int N_idea[MaxN][MaxL];
int n;
int m;
int t;
int l;
#define debug 0
void init(void)
{
    int n;
    int k;
    for (n=0; n<1<<16; ++n)
    {
        int temp = n;
        int sum(0);
        while (temp != 0)
        {
            sum += temp % 2;
            temp /= 2;
        }
        f[n] = sum;
    }
    return;
}
bool dfs(int k)
{
    int i;
    int temp;
    for (i=0; i<m; ++i)
    {
        if (graph[k][i] && !visit[i])
        {
            visit[i] = true;
            temp = match[i];
            if (temp == -1 || dfs(temp))
            {
                match[i] = k;
                return true;
            }
        }
    }
    return false;
}
int main(void)
{
    int i;
    int j;
    int k;
    int num;
    int id;
    init();
#if debug
    freopen("in.txt", "r", stdin);
#endif
    while (scanf("%d %d %d %d", &n, &m, &t, &l) != EOF)
    {
        memset(N_idea, 0, sizeof(N_idea));
        memset(D_idea, 0, sizeof(D_idea));
        memset(graph, false, sizeof(graph));
        for (i=0; i<n; ++i)
        {
            scanf("%d", &num);
            for (j=0; j<num; ++j)
            {
                scanf("%d", &id);
                --id;
                D_idea[i][id/32] += 1u << (id % 32);
            }
        }
        for (i=0; i<m; ++i)
        {
            scanf("%d", &num);
            for (j=0; j<num; ++j)
            {
                scanf("%d", &id);
                --id;
                N_idea[i][id/32] += 1u << (id % 32);
            }
        }
        //initial graph
        for (i=0; i<n; ++i)
        {
            for (j=0; j<m; ++j)
            {
                num = 0;
                for (k=0; k<MaxL; ++k)
                {
                    unsigned int temp = D_idea[i][k] & N_idea[j][k];
                    num += f[temp >> 16] + f[temp & 0x0000ffff];
                }
                if (num >= l)
                {
                    graph[i][j] = true;
                }
            }
        }
        num = 0;
        memset(match, -1, sizeof(match));
        for (i=0; i<n; ++i)
        {
            memset(visit, false, sizeof(visit));
            if (dfs(i))
            {
                ++num;
            }
        }
        printf("%d\n", n + m - num);
    }
    return 0;
}

[by delta_4d]