题解 AT4144 【[ARC098D] Donation】

· · 题解

题意 ： 给出一张 n 个点 m 条边的无向连通图。

点 u 有两参数 A_u,B_u。当你经过该点时，必须至少拥有 A_u 元，在该点打卡需要花费 B_u 元。

你可以从任意点开始旅程。你需要在所有点打卡一次，问初始时最少需要携带多少元。

------------ 很有意思的一个题。 - **性质** ： 在某点打卡后必不会再次访问某点。 **解释** ：不难发现，旅行中的钱数是单调不增的。 若两次访问某点，第一次不打卡，第二次打卡要比第一次就打卡优，因为中间的一段路程余钱更多。 若遵守上述策略，令 $C_u=\max(A_u-B_u,0)$ ，约束可以等价于 ： 在 $u$ 点的所有时刻钱数都 $\geq C_u$。 一种直观的想法是 ： 按照 $C$ 排序，并按顺序打卡。 可惜的是，在点之间移动时，受到图的限制，途中可能经过 $C$ 更大的节点。 我们将 $u\rightarrow v$ 的边权设为 $\max(C_u,C_v)$ ，求最小生成树，不难发现最优的移动路径只会在最小生成树上，这样就把图简化成了树。 最小生成树的性质仍然不够好（边上的 $C$ 是乱序的），考虑建立重构树。 观察边权的性质，根据 $\rm Kruskal$ ，建树的过程等价于按照 $C$ 从小到大枚举点 $u$ ，然后尽量加入和 $C$ 更小的点 $v$ 连接的边。 我们连边 （$u\rightarrow v$ 目前的最浅祖先）。这样就建立了类似重构树的结构，满足下面两条关键性质 ： - 深度越深， $C$ 越小。 - 两点间路径的 $\max C$ 取得最小值。 接下来在树上 $\rm DP$。 设 $dp[u]$ 为处理完 $u$ 子树（不必回到 $u$）所需的初始钱数，$s[u]$ 为子树内 $B$ 的和。 对于叶节点，显然有 $dp[u]=B_u+C_u$。 对于非叶节点，若有 $k$ 个子树，要先处理 $k-1$ 个，然后在 $u$ 打卡，然后处理最后一个。 在处理前面 $k-1$ 个时，由于树中的 $C$ 上大下小，而钱单调不增，所以只需要考虑在 $u$ 打卡的一次约束。 枚举最后进入的子树 $v$ ，则有 $dp[u]=\min\limits_{u\rightarrow v}(s[u]-s[v]+\max(C_u,dp[v]))

其中，s[u]-s[v] 是处理前面 k-1 个子树的花费，\max(C_u,dp[v]) 是后面的限制。

#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 105000
using namespace std;
struct UFS{
  int f[MaxN];
  void Init(int n)
  {for (int i=1;i<=n;i++)f[i]=i;}
  int find(int u)
  {return f[u]==u ? u : f[u]=find(f[u]);}
  bool merge(int u,int v){
    u=find(u);v=find(v);
    if (u==v)return 0;
    f[u]=v;return 1;
  }
}F;
vector<int> g[MaxN],org[MaxN];
ll dp[MaxN],s[MaxN];
int c[MaxN],b[MaxN];
void pfs(int u)
{
  s[u]=b[u];
  for (int i=0;i<g[u].size();i++){
    pfs(g[u][i]);
    s[u]+=s[g[u][i]];
  }
}
void dfs(int u)
{
  if (!g[u].size())dp[u]=b[u]+c[u];
  else dp[u]=1ll<<60;
  for (int i=0,v;i<g[u].size();i++){
    dfs(v=g[u][i]);
    dp[u]=min(dp[u],s[u]-s[v]+max((ll)c[u],dp[v]));
  }
}
bool cmp(int A,int B)
{return c[A]<c[B];}
int n,m,p[MaxN];bool vis[MaxN];
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
      scanf("%d%d",&c[i],&b[i]);
      c[p[i]=i]=max(c[i]-b[i],0);
    }for (int i=1,u,v;i<=m;i++){
      scanf("%d%d",&u,&v);
      org[u].pb(v);org[v].pb(u);
    }
  sort(p+1,p+n+1,cmp);
  F.Init(n);
  for (int t=1;t<=n;t++){
    int u=p[t];
    for (int i=0,v;i<org[u].size();i++)
      if (vis[v=org[u][i]]){
        v=F.find(v);
        if (F.merge(v,u))g[u].pb(v);
      }
    vis[u]=1;
  }
  pfs(p[n]);dfs(p[n]);
  printf("%lld",dp[p[n]]);
    return 0;
}