「题解」「国家集训队互测」家族

题目链接:GMOJ 3301/Tsinsen-A1491。

题目

题目描述

阿狸和桃子养了 $n$ 个小阿狸,小阿狸们每天都在一起玩的很开心。作为工程师的阿狸在对小阿狸们之间的关系进行研究以后发现了小阿狸的人际关系由某种神奇的相互作用决定,阿狸称之为“键”。每个键有一个频率,称为键频率,是一个整数(单位 $\text{Hz}$)。

由于小阿狸们每天成集团地黏在一起,桃子希望他们能够分成更加独立的几团。阿狸发现,一旦小阿狸们分开,独立的一块连在一起的几个小阿狸就会形成一个家族,而家族的类型由这个家族的小阿狸的数量唯一确定(比如说只有一个小阿狸的家族显然就是单身码农,两个小阿狸的显然是一对小阿狸恋人,三个小阿狸的就是三口之家等等)。显然,一个小阿狸和另一个小阿狸处于同一家族,当且仅当两个小阿狸之间存在直接或间接的键组成的路径。

桃子对每种小阿狸家族都有自己的喜好程度,她希望所有的小阿狸家族喜好程度之和大于等于 $K$。

为了让小阿狸们分开来,阿狸决定让某些键断裂,只保留某一段频率的键,比如说 $100\text{Hz}$ 到 $140\text{Hz}$ 频率的键, 这时频段宽度为 $40\text{Hz}$。当然,阿狸希望频段宽度越小越好,但至少要有一个小键。你的任务就是求出最小的频段宽度。

注意,输入不保证全部键都有效时只有一个小阿狸家族。

输入格式

第一行 $3$ 个整数 $n(n\leq 1000), m(m\leq 5000), K(0\leq k\leq 2^{31}-1)$。
接下来 $1$ 行 $n$ 个整数,第 $i$ 个整数表示桃子对大小为 $i$ 的小阿狸家族的喜爱程度。
接下来 $m$ 行,每行 $3$ 个整数 $u,v,f$。表示 $u$ 小阿狸和小阿狸 $v$ 之间存键,频率 $f\text{Hz}$。

输出格式

一个整数,即最窄的频段宽度(不存在可行频段,输出 T_T,不含引号)。

样例输入输出

#1

  • Input:
4 4 52
1 50 2 9
1 2 6
2 3 8
3 4 4
1 4 3
  • Output:
0

#2

  • Input:
4 4 10
1 5 2 9
1 2 6
2 3 8
3 4 4
1 4 3
  • Output:
2

#3

  • Input:
4 4 10
1 4 2 9
1 2 6
2 3 8
3 4 4
1 4 3
  • Output:
T_T

题解

思路

很显然,如果我们将每一个键按照频率 $f$ 排序,那么可以发现,本质不同的频段就只有 $\frac{m(m+1)}{2}$ 个,所以我们选择枚举每一个频段(时间复杂度为 $\Theta(m^2)$),再花费 $\Theta(1)$ 的时间来维护并统计答案。

我们这里维护和统计答案的过程应该使用并查集(路径压缩+按秩合并)来实现(这样优化后的并查集的时间复杂度为 $\Theta(\alpha(n))$,其中 $\alpha(x)$ 是反阿克曼函数,$\forall x\in\mathbb{N_+},x\leq 2^{2^{10^{19729}}}$,都有 $\alpha(x)\leq 4$ ,所以这种并查集的时间复杂度可近似看作 $\Theta(1)$。

另外,我们还要记录每一个集合的大小,方便统计。

合并时也要采用 $\Theta(1)$ 的方法,先减掉两个即将合并集合的贡献,再合并,加上新集合的贡献。

具体的实现看代码。

代码

具体实现的一些细节都已经使用注释标出,请仔细查看。

#include<cstdio>
#include<algorithm>
using std::min;
using std::sort;
typedef long long ll;
#define INF 0X3F3F3F3F3F3F3F3Fll
//以上为头文件和一些定义
const int MAXN=1000+5;
const int MAXM=5000+5;
//最大数据范围
struct Node{//Node用于存储键
    int u,v;
    ll f;
    void Read(void){//读入函数
        scanf("%d%d%lld",&u,&v,&f);
        return;
    }
    bool operator<(const Node &a)const{//重载小于运算符,方便排序
        return f<a.f;
    }
};
int n,m;
int fa[MAXN];
ll K;
ll love[MAXN];
ll size[MAXN];
Node a[MAXM];
int find(int x){//路径压缩的优化
    if(x==fa[x])
        return x;
    else
        return fa[x]=find(fa[x]);
}
void merge(int a,int b){//为什么这没有用按秩合并呢?因为我懒
    register int ra=find(a),rb=find(b);
    if(ra!=rb)
        fa[rb]=ra;
    return;
}
bool search(int a,int b){
    return find(a)==find(b);
}
int main(void){
    register int i,j;
    register ll sum,ans=INF;
    scanf("%d%d%lld",&n,&m,&K);
    for(i=1;i<=n;++i)
        scanf("%lld",&love[i]);
    for(i=1;i<=m;++i)
        a[i].Read();
    sort(a+1,a+m+1);//排序
    for(i=1;i<=m;++i){//枚举
        sum=love[1]*n;
        for(j=1;j<=n;++j)
            fa[j]=j,size[j]=1;
        for(j=i;j<=m;++j){//注意是从i开始枚举
            if(!search(a[j].u,a[j].v)){//O(1)的修改操作
                sum-=love[size[find(a[j].u)]]+love[size[find(a[j].v)]];//减掉两个即将合并集合的贡献
                size[find(a[j].u)]+=size[find(a[j].v)];
                sum+=love[size[find(a[j].u)]];//合并,加上新集合的贡献
                merge(a[j].u,a[j].v);
            }
            if(sum>=K){
                ans=min(ans,a[j].f-a[i].f);//更新答案
            }
        }
    }
    if(ans!=INF)
        printf("%lld\n",ans);//输出
    else
        puts("T_T");
    return 0;
}