526互联

[ARC098F] Donation 题解

发布时间 2023-11-03 16:46:08作者: Ehundategh

[ARC098F] Donation 题解

题目描述

给定一张 \(n\) 点，\(m\) 边的无向图，到达一个点需要拥有 \(a_i\) 的权值，对于一个点操作需要消耗 \(b_i\) 的权值，询问最少需要多少权值才能够对每个点都进行一次操作（权值在任何时候都不能小于 \(0\)）。

题目分析

提供一个真正无脑的方案。

首先考虑每个点消耗权值并不好处理，我们将消耗权值改成逆过程，即获取权值，那么问题转化为到达一个点会获得 \(b_i\) 的权值，并且经过一个点需要至少 \(Cost_i=\max(a_i-b_i,0)\) 的权值，最少需要多少初始权值，此时原题答案就是求出的值加上所有点的 \(b_i\) 之和。

那么对于最少初始权值的求解，我们直接二分答案。

首先考虑处理经过一个点需要的权值，要限定可以走的节点，我们直接将每条边的边权赋成 \(\max(Cost_u,Cost_v)\) 并且以此建立一棵重构树。那么此时我们从根节点进行遍历即可，对于每一个节点判断。如果当前点是不是叶子节点，判断其是否存在一个子树满足给定初始值加上子树中所有叶子节点的 \(b_i\) 大于等于当前点的限制。而对于叶子节点，我们只需要判断初始值加上其 \(b_i\) 能否满足其限制。这种做法就可以完全舍弃 \(\texttt{dp}\) 直接求解。

注意：要考虑点数为 \(1\) 边数为 \(0\) 的情况，因为这种情况下是没有办法建立重构树的，所以要特别判断。

代码

/*
 * @Author: Ehundategh
 * @Date: 2023-11-03 11:43:20
 * @FilePath: \Code\11.3\[ARC098F] Donation.cpp
 * @Description: You Steal,I Kill
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LSon Node[Now].LeftS
#define RSon Node[Now].RightS
#define MAXN 100010
using namespace std;
int Head[MAXN],Total=0,n,m,cnt=0;
long long Sum=0;
int A[MAXN],B[MAXN];
int Fa[MAXN<<1];
struct edge{
    int St,Ed,Value;
}Edge[MAXN];
bool cmp(edge a,edge b){return a.Value<b.Value;}
struct node{
    int LeftS,RightS;
    long long Get,Limit;
    int Father;
}Node[MAXN<<1];
int Find(int x){return Fa[x]==x?x:Fa[x]=Find(Fa[x]);}
void Merge(int a,int b,int c,int Value){
    Node[c].Limit=Value;
    Node[a].Father=c;Node[b].Father=c;
    Node[c].LeftS=a,Node[c].RightS=b;
    Node[c].Get=Node[a].Get+Node[b].Get;
    Fa[a]=c;Fa[b]=c;
}
void Kruskal(){
    sort(Edge+1,Edge+m+1,cmp);cnt=n;
    for(int i=1;i<=2*n;i++) Fa[i]=i;
    for(int i=1;i<=m;i++){
        int x=Edge[i].St,y=Edge[i].Ed;
        if(Find(x)==Find(y)) continue;
        Merge(Find(x),Find(y),++cnt,Edge[i].Value);
    }
    return;
}
long long DFS(int Now,long long Start){
    if(Now<=n) return Start+Node[Now].Get>=Node[Now].Limit?Start+Node[Now].Get:0;
    long long GL=DFS(LSon,Start),GR=DFS(RSon,Start);
    if(!(GL||GR)) return 0;
    long long Max=max(GL,GR);
    return Max>=Node[Now].Limit?Node[Now].Get+Start:0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&A[i],&B[i]);
        Node[i].Get=B[i];
        Sum+=1ll*B[i];
    }
    if(n==1) {printf("%d\n",A[1]);return 0;}
    for(int i=1;i<=m;i++){
        scanf("%d%d",&Edge[i].St,&Edge[i].Ed);
        Edge[i].Value=max(max(A[Edge[i].St]-B[Edge[i].St],0),max(A[Edge[i].Ed]-B[Edge[i].Ed],0));
    }
    Kruskal();
    long long L=0,R=1ll<<50;
    while(L<R){
        long long Mid=(L+R)>>1;
        if(Mid==R) Mid--;
        if(DFS(cnt,Mid)) R=Mid;
        else L=Mid+1;
    }
    printf("%lld\n",L+Sum);
}