10.14总结

· · 个人记录

放个差传点在这
apple365怎么这么坏啊难度从后往前

T1

简化题意就是给所有的犯人分成两堆使这两堆的仇恨值最大值最小
本题最坑是：敌人的敌人不一定是我的敌人，所以这里直接pass普通并查集，只能用种类并查集
我们使用最值生成树的时候，要使怨气最大值最小，所以我们要尽量让两个怨气大的远离，排序的时候要把怨气大的放在前面，然后枚举每一条边，如果这两个还没分配监狱，就将他们拆开，否则这就是两个监狱的怨气最大值 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+7;
int n,m;
int fa[maxn];
int find(int x) {
    if(fa[x]==x) {
        return x;
    }
    return fa[x]=find(fa[x]);
} 
void unionn(int u,int v) {
    int x=find(u),y=find(v);
    if(x!=y) {
        fa[x]=y;
    }
}
struct Node{
    int u,v,w;
}edge[maxn];
bool cmp(Node a,Node b) {
    return a.w>b.w;
} 
int ans=0;
void kruskal() {
    for(int i=0;i<maxn;i++) {
        fa[i]=i;
    }
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=m;i++) {
        int u=find(edge[i].u);
        int v=find(edge[i].v);
        if(u==v) {
            cout<<edge[i].w;
            exit(0);
        } else {
            unionn(edge[i].u+n,edge[i].v);
            unionn(edge[i].u,edge[i].v+n);
        }
    }
    cout<<0<<'\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
    }
    kruskal();
    return 0;
}
//A

T2

首先二维不方便进行并查集，所以转成一维，公式为

(x-1)*n+y

然后就开始跑并查集，如果这一个点之前走过说明已经有环了，直接输出，否则给这两个点并上继续去找

T3

首先跑一编埃氏筛筛出a到b中所有的质数，然后枚举a到b，再枚举每一个质数，如果这个质数>p并且可以被整除就用并查集并上
最后枚举a到b看有几个不同的父亲就可以了

T4

并查集板子题但是题开都没开，把x和i并上如果fa[i]==i钥匙不在i位置，cnt加上就可以了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int fa[maxn],n;
int find(int x) {
    if(fa[x]==x) {
        return x;
    }
    return fa[x]=find(fa[x]);
}
void unionn(int u,int v) {
    int x=find(u),y=find(v);
    if(x!=y) {
        fa[x]=y;
    }
}
signed main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        fa[i]=i;
    }
    for(int i=1; i<=n; i++) {
        int x;
        cin>>x;
        unionn(x,i);
    }
    int sum=0;
    for(int i=1; i<=n; i++) {
        sum+=(fa[i]==i);
    }
    cout<<sum;
    return 0;
}