gym102331f 题解

Grisses · 2024-11-13 17:07:45 · 题解

题面

据说是减半报警器最早出现的地方。

先用一个堆维护所有被激活的边，然后用并查集维护联通块。

对于一条边，如果 w_u+w_v\ge s，则有 \max(w_u,w_v)\ge\lceil\dfrac s2\rceil。对每个连通块维护一个堆记录一端在这个连通块里的边的阈值即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,w[300005],fa[300005];
struct edge{
    int u,v,w;
}e[300005];
int tog,las[300005],stp[300005];
struct node{
    int val,id,tim;
    bool operator<(const node &t)const{return val>t.val;}
};
priority_queue<node>q[300005];
int find(int x){
    if(fa[x]==x)return fa[x];
    else return fa[x]=find(fa[x]);
}
priority_queue<int,vector<int>,greater<int> >qq;
void Sol(node tmp){
    int p=tmp.id;
    if(find(e[p].u)==find(e[p].v))return;
    int sum=w[find(e[p].u)]+w[find(e[p].v)];
    if(stp[p]+e[p].w<=sum){
        qq.push(p);
        las[p]=-1;
        return;
    }
    e[p].w=stp[p]+e[p].w-sum;
    stp[p]=sum;
    int l=(e[p].w+1)/2;
    las[p]=++tog;
    q[find(e[p].u)].push(node({w[find(e[p].u)]+l,p,tog}));
    q[find(e[p].v)].push(node({w[find(e[p].v)]+l,p,tog}));
}
void ch(int id){
    while(!q[id].empty()&&q[id].top().val<=w[id]){
        node tmp=q[id].top();
        q[id].pop();
        if(tmp.tim!=las[tmp.id])continue;
        Sol(tmp);
    }
}
vector<int>ans;
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w);
        if(w[e[i].u]+w[e[i].v]>=e[i].w)qq.push(i),las[i]=-1;
        else{
            las[i]=++tog;
            stp[i]=w[e[i].v]+w[e[i].u];
            e[i].w-=w[e[i].v]+w[e[i].u];
            int l=(e[i].w+1)/2;
            q[e[i].u].push(node({w[e[i].u]+l,i,tog}));
            q[e[i].v].push(node({w[e[i].v]+l,i,tog}));
        }
    }
    for(int i=1;i<=n;i++)fa[i]=i;
    while(!qq.empty()){
        int tmp=qq.top();
        qq.pop();
        int c=find(e[tmp].u),d=find(e[tmp].v);
        if(c==d)continue;
        ans.push_back(tmp);
        if(q[c].size()>q[d].size())swap(c,d);
        fa[c]=d;
        w[d]+=w[c];
        while(!q[c].empty()){
            node tmp=q[c].top();
            q[c].pop();
            if(tmp.tim!=las[tmp.id])continue;
            q[d].push(tmp);
        }
        ch(d);
    }
    printf("%lld\n",(int)ans.size());
    for(int x:ans)printf("%lld ",x);
    return 0;
}