并查集

游戏

lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次？

题目链接：
==https://nanti.jisuanke.com/t/T2650==

现在也没有想太通为什么这题用并查集写..先挖个坑吧，说不定以后学的多了就渐渐明白了..
题解参考博客地址：http://hzwer.com/2950.html

把一个有a,b两种属性的武器看成点a，b之间的无向边
对于一个联通块，假如不含环（就是一棵树），那么必定可以满足其中任意的p-1个点。
对于一个联通块，假如含环，那么必定全部的p个点都能满足。
那么合并并查集的时候可以利用一个vis来维护这个性质
把权值看成点，把武器看成边， 如果每次加入的边是合并两个联通块 就把权值小的联通块并到权值大的联通块，然后给权值小的vis=true 如果不是就把该联通块的顶点的vis=true
这样就可以保证，如果一个大小为N联通块 =N-1条边构成，最大点的vis=false，其他为true；≥N条边构成，所有点的vis=true
然后最后只要一次扫描vis就可以得出答案了

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+50;

int n,f[N];
bool vis[N];

int found(int x){
    if(f[x]==x)return x;
    return f[x]=found(f[x]);
}

void unit(int x,int y){
    if(x>y)swap(x,y);
    if(vis[x]==1)vis[y]=1;
    vis[x]=1;
    f[x]=y;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=10000;i++){
        f[i]=i;
    }
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x=found(x),y=found(y);
        if(x==y)vis[x]=1;
        else unit(x,y);
    }
    for(int i=1;i<=10001;i++){
        if(!vis[i]){
            printf("%d\n",i-1);
            return 0;
        }
    }
}

Supermarket

题目链接：==http://poj.org/problem?id=1456==

超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.
每天只能卖一个商品.
现在你要让超市获得最大的利润.

题解参考博客：https://blog.csdn.net/shuangde800/article/details/8022068

因为每卖一个产品要占用一个时间单位，所以，我们可以一个单位一个单位时间地依次决定，每个时间要卖哪个产品，并且保证每个单位时间卖出的产品都是利润最大的，这样便能保证最终结果是最大的。从最后一个截至时间开始往前枚举， 这样的话，只要把截止时间大于这个时间段的产品都放入优先队列，其中利润最大的便是这时间所要的。

先把所有产品按照利润从大到小排序，然后这个把这个放在截止日期那天卖出，并做好标记，如果截至日期那天已经有其他产品占用了，那么可以把这个产品卖出的时间往前推，直到找到可以卖的那一天并标记好。用并查集的关键之处是，我们知道按照上面那个方法，假设一个产品a占用了一个日期后，那么如果下次又有一个产品b和产品a的截止日期是相同的，但是那个日期以被占用了，所以就要往前移动1天，那么就可以用并查集进行标记，在a占用了那个日期后，把a的截止日期指向前一个日期，这样的话，可以直接查找到他要占用到哪一个时间。

代码：
贪心+优先队列（法一）按截止时间

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e4+50;

struct node{
    int p,d;
    bool operator <(const node &rhs)const{
        return d>rhs.d;
    }
}v[N];



int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        priority_queue<int> Q;
        int max_time=0;
        for(int i=0;i<n;i++){
            int p,d;
            scanf("%d%d",&p,&d);
            v[i]=(node){p,d};
            max_time=max(max_time,d);
        }
        sort(v,v+n);
        int cnt=0;
        long long sum=0;
        for(int i=max_time;i>=1;i--){
            for(;cnt<n;cnt++){
                if(v[cnt].d>=i){
                    Q.push(v[cnt].p);
                }
                else break;
            }
            if(!Q.empty()){
                sum+=Q.top();
                Q.pop();
            }
        }
        printf("%lld\n",sum);
    }
}

63ms
法二：按利润排序

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e4+50;

struct node{
    int p,d;
    bool operator <(const node &rhs)const{
        return p>rhs.p;
    }
}v[N];

bool vis[N]={0};

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            int p,d;
            scanf("%d%d",&p,&d);
            v[i]=(node){p,d};
        }
        sort(v,v+n);

        fill (vis,vis+N,0);
        long long sum=0;
        for(int i=0;i<n;i++){
            for(int j=v[i].d;j>=1;j--){
                if(!vis[j]){
                    vis[j]=1;
                    sum+=v[i].p;
                    break;
                }
            }
        }
        printf("%lld\n",sum);
    }
}

用并查集优化

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e4+50;

struct node{
    int p,d;
    bool operator <(const node &rhs)const{
        return p>rhs.p;
    }
}v[N];

int f[N];
bool vis[N];

void init(){
    for(int i=1;i<N;i++){
        f[i]=i;
    }
}

int found(int x){
    if(f[x]==x)return x;
    return f[x]=found(f[x]);
}


int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            int p,d;
            scanf("%d%d",&p,&d);
            v[i]=(node){p,d};
        }
        init();
        sort(v,v+n);
        fill (vis,vis+N,0);
        long long sum=0;
        for(int i=0;i<n;i++){
            int m=found(v[i].d);
            if(m>0){
                sum+=v[i].p;
                f[m]=m-1;
            }
        }
        printf("%lld\n",sum);
    }
}