[ARC098F] Donation 题解

hegm · 2023-01-09 20:47:17 · 题解

[ARC098F] Donation

第二次遇见在 \text{Kruskal} 重构树上跑 \text{dp} 。

很烦，题目和 Labyrinth十分相似，但是不在是边权，而是点权。

考虑两个点的先后顺序 ，两点为 u,v 。 sum 表示当前的钱数。s 为限制， c 为花费。（保证 sum>c_u+c_v ）

两个条件：

① sum-c_u\ge s_v 可以先去 u 再去 v。

② sum-c_v\ge s_u 可以先去 v 再去 u。

大力分讨：

1. ① \& ② 两者不需要考虑顺序。

2. ① \& !② 必须先去 u 才能再去 v。

对于情况 2. 我们满足

• sum-c_u\ge s_v \ \ \ \& \ \ \ \ sum-c_v<s_u
• sum\ge s_v+c_u \ \ \ \& \ \ \ \ sum<s_u+c_v

• 将两者合并, s_u+c_v >sum\ge s_v+c_u

• s_u+c_v > s_v+c_u

• 移项 s_u-c_u > s_v-c_v

我们发现，哎！这样的话每个数之和自己有关系了，太好了。

那么设 t_i=s_i-c_i

我们第一时间想到的是按 t_i 排序，然后就做完了，好的，你就错完了。

对于每条边，我们将它的边权设置为 \max(t_u,t_v) 。

我们从叶子节点开始合并。

具体可以看代码。

\text{CODE}

#include<bits/stdc++.h>
#define N 5000005
#define int long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,a[N],cnt,f[N],sum[N],ans[N],b[N];
struct edge 
{
    int u,v,w;
}e[N*2];
int find(int now)
{
    if(f[now]==now)return now;
    return f[now]=find(f[now]);
}
bool cmp(edge a,edge b){return a.w<b.w;}
signed main()
{
    n=read(),m=read();cnt=n;
    for(int i=1;i<=n;i++)a[i]=read(),b[i]=read(),a[i]=max(a[i]-b[i],0ll);
    for(int i=1;i<=m;i++)
    {
        e[i].u=read();
        e[i].v=read();
        e[i].w=max(a[e[i].u],a[e[i].v]);
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=2*n;i++)f[i]=i,ans[i]=a[i]+b[i],sum[i]=b[i];
    for(int i=1,u,v;i<=m;i++)
    {
        u=find(e[i].u);v=find(e[i].v);
        if(u!=v)
        {
            ++cnt;
            f[u]=f[v]=cnt;
            ans[cnt]=min(max(e[i].w,ans[v])+sum[u],max(e[i].w,ans[u])+sum[v]);
            sum[cnt]=sum[u]+sum[v];
        }
    }
    cout<<ans[cnt]<<"\n";
    return 0;
}

当然，你做完这道题也可以去看看Labyrinth。