Supermarket 【POJ - 1456】【并查集+哈希表思想+贪心】

题目链接

  原来，并查集还有这样的作用——题记。

  我想用个哈希表的思维来解这道题，但是，显然O(N^2)的哈希表去查询并插入显然是不行的，那么既然挂在图论专题，我就得用相应的方式解答咯（要是不挂在图论专题，我可能会自闭了），我们对于每个物品按照价值降序排列，要的就是价值高的物品先放进哈希表中，但是，怎么确定这个点的值是否已经有值了？

  我们用到了并查集，对于可以放进哈希表中的值，相当于，我们可以把他的时间与前一刻的时间连立起来，就是意味着这个点已经用过了，时间到了前面的那个时间（不一定就是前面的时间，是指的是前一个空的时间），用并查集。那么判断是否可以用，就是判断，它的时间点是否可以用，只要前面的还有空位就是可以放进去，时间点不为0就是前面有空位，那么就是并查集找到的祖先不是0就行了。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define efs 1e-7
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e4 + 7;
int N, root[maxN], sum[maxN], ans;
struct node
{
    int val, day;
    node (int a=0, int b=0):val(a), day(b) {}
}a[maxN];
bool cmp(node e1, node e2) { return e1.val == e2.val?(e1.day < e1.day):(e1.val > e2.val); }
int fid(int x) { return x == root[x]?x:(root[x] = fid(root[x])); }
void mix(int x, int y)
{
    int u = fid(x), v = fid(y);
    if(u != v)
    {
        if(u > v) swap(u, v);
        root[v] = u;
    }
}
void init()
{
    for(int i=0; i<maxN; i++) root[i] = i;
    memset(sum, 0, sizeof(sum));
    ans = 0;
}
int main()
{
    while(scanf("%d", &N)!=EOF)
    {
        init();
        for(int i=1; i<=N; i++)
        {
            scanf("%d%d", &a[i].val ,&a[i].day);
        }
        sort(a+1, a+1+N, cmp);
        for(int i=1; i<=N; i++)
        {
            int x = a[i].day;
            int u = fid(x);
            if(u >= 1)
            {
                mix(x, u-1);
                ans += a[i].val;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}