POJ 2239 哈希取址+二分匹配

5
1 1 1
2 1 1 2 2
1 2 2
2 3 2 3 3
1 3 3

4

这题刚开始理解题目错了，尼玛，看到样例中1 1有几个，所以还以为是重复的呢，就只取了一个，然后就剩下（1，1），（2，2），（3，2），（3，3），然后就得出样例答案为4.。直接WA一发，然后又重新读题才发现理解错题意了，晕……

题意原来是当前课程会在那些时间上几次课，刚开始因为当前是一个结点了，然后周数与节数又有两个数据，所以想想这两个如果要想放在图论中，那么当然得把这两个数据合成一个地址……哈哈这么想着就有思路了……因为以前做过哈希方面的题，所以保存了好多哈希取址的计算函数，在实际中用得最多最高效也是最容易的就是BKDRHash哈希函数了，其计算式为：a*131+b这个就作为一个新地址存下来，也就是另一个结点……因为这个计算式已经被好多人证实过了，对于全部的（a,b），其取唯一地址的函数可以用这个计算，这个函数在实际中也是证明被用得最多的了，当然这个没有处理地址冲突，所以地址还是有bug的，但是就这水题这个式子够了……

然后有了这两个结点当然就可以做边了，匹配就是二分匹配了……

哈希不懂的可以看我的另一篇博文：http://blog.csdn.net/u011466175/article/details/17484687

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1000005
#define MN 100010
#define INF 55566677
#define eps 1e-7
using namespace std;
typedef long long ll;
vector<int>v[MN];
int vis[MN],pre[MN];
int dfs(int u)
{
    for(int i=0; i<v[u].size(); i++)
    {
        int j=v[u][i];
        if(!vis[j])
        {
            vis[j]=1;
            if(!pre[j]||dfs(pre[j]))
            {
                pre[j]=u;
                return 1;
            }
        }
    }
    return 0;
}
int solve(int n)
{
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        mem(vis,0);
        ans+=dfs(i);
    }
    return ans;
}
int main()
{
    int n,m,i,j,p,q;
    while(~sca(n))
    {
        for(i=0;i<=n;i++) v[i].clear();
        mem(pre,0);
        for(i=1;i<=n;i++)
        {
            sca(m);
            while(m--)
            {
                scanf("%d%d",&p,&q);
                int cnt=p*131+q;//BKDRHash哈希取址计算式即可
                v[i].push_back(cnt);
            }
        }
        pri(solve(n));
    }
    return 0;
}

POJ 2239 哈希取址+二分匹配,布布扣,bubuko.com

POJ 2239 哈希取址+二分匹配

原文：http://blog.csdn.net/u011466175/article/details/22698975