题解：P17364 [ECNA 2024] Pony-less Express

· · 题解

题意简述

以首都 0 为根的一棵树，每个节点收到消息后，必须在随后连续的若干天中，每天向一个尚未收到消息的子节点传递消息。

农庄 u 在第 t 天收到消息时，代价为 c_u(d_u-t)^2。首都在第 0 天已有消息，求所有农庄的最小总代价。

解题思路

一个节点能够决定的是子节点的通知顺序。不同子树使用各自的马匹，收到消息后的工作相互独立。因此，固定节点收到消息的日期后，仅需把不同子树分配到连续的日期上。

设 u 有 m 个子节点，收到消息的日期为 t。其子节点必须分别在 t+1,t+2,\dots,t+m 收到消息，不能省略中间日期，也不能在同一天通知两个子节点。这里的日期按题目示例计数：首都第 1 次传递消息，对应子节点第 1 天收到消息。

定义 f_{u,t} 为 u 在第 t 天收到消息时，整个 u 子树的最小代价。令首都的 c_0=d_0=0，便能与农庄使用相同转移。设子节点为 v_1,v_2,\dots,v_m，用排列 \pi 表示第 j 个被通知的子节点，则有：

f_{u,t}=c_u(d_u-t)^2+\min_\pi\sum_{j=1}^m f_{v_{\pi_j},t+j}

直接枚举排列不可行，但每个子节点与每个通知次序之间的代价已经确定。建立一个二分图：左侧为 m 个子节点，右侧为 1\sim m 的通知次序，从 v_i 到次序 j 的边权为 f_{v_i,t+j}。最小权完美匹配恰好给出上述最小值。

这个对应是双向的。任意合法通知顺序都让每个子节点和每个次序各使用一次，因而形成完美匹配。反过来，匹配可以直接排列成连续的通知次序，各子树再执行自身最优方案，不会争用其他子树的马匹。因此，匹配没有放宽限制，也没有遗漏最优方案。

实现中按子树从下往上计算，矩阵 a 保存当前二分图的边权，match 用匈牙利算法求最小权完美匹配。p[j] 保存右侧位置 j 匹配的左侧节点，x 和 y 保存两侧势能；dis 维护增广过程中尚未加入交错树的右侧节点的最小剩余边权。每次调整势能使至少一条候选边的剩余权变为 0，再沿 pre 记录的路径增广。这里只需要标准的最小权匹配，子树代价不要求单调或满足额外性质。叶节点对应空匹配，贡献为 0。

日期范围也可以在向下遍历时确定。设节点 u 的可能到达日期在区间 [l,r] 内，则每个子节点的日期范围为 [l+1,r+m]。根节点从 [0,0] 开始。路径上每经过一个父节点，到达日期增加该节点为当前子节点安排的次序；这些次序的选择分别发生在不同节点，可以独立进行。若父节点可取连续区间内的任意日期，再加上 1\sim m，子节点也能取上述新区间内的任意日期。

任意一条根到节点的路径上，各父节点的子节点集合互不相交。通知次序至多为对应父节点的子节点数，所以路径上所有次序之和不超过 n。因此，所有日期均在 0\sim n 内，二维数组大小为 O(n^2) 即可。代码中 dfs(u,l,r) 先计算所有子节点，再填充该范围内的 f_{u,t}，答案为 f_{0,0}。

设节点 u 的子节点数为 m_u，计算的日期数为 w_u。匹配部分的总时间为 O(\sum_u w_um_u^3)；由 w_u\le n+1 和 \sum_u m_u=n，可得最坏时间复杂度 O(n^4)。代码仅计算实际可能日期，链上的节点各仅有一个状态，根节点也仅有一个状态。空间复杂度为 O(n^2)。每个农庄的代价不超过 20n^2，总和不超过 20n^3，在本题范围内可以使用 int。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=205;
const int inf=0x3f3f3f3f;
int c[N],d[N],f[N][N],a[N][N],x[N],y[N],p[N],pre[N],dis[N];
bool vis[N];
vector<int> G[N];
int match(int n)
{
    fill(x,x+n+1,0);
    fill(y,y+n+1,0);
    fill(p,p+n+1,0);
    for(int i=1;i<=n;i++)
    {
        p[0]=i;
        fill(dis,dis+n+1,inf);
        fill(vis,vis+n+1,0);
        int u=0;
        do
        {
            vis[u]=1;
            int v=0,mn=inf;
            for(int j=1;j<=n;j++)
            {
                if(vis[j])continue;
                int val=a[p[u]][j]-x[p[u]]-y[j];
                if(val<dis[j]){dis[j]=val;pre[j]=u;}
                if(dis[j]<mn){mn=dis[j];v=j;}
            }
            for(int j=0;j<=n;j++)
            {
                if(vis[j]){x[p[j]]+=mn;y[j]-=mn;}
                else dis[j]-=mn;
            }
            u=v;
        }while(p[u]);
        while(u)
        {
            p[u]=p[pre[u]];
            u=pre[u];
        }
    }
    return -y[0];
}
void dfs(int u,int l,int r)
{
    int m=G[u].size();
    for(auto v:G[u])dfs(v,l+1,r+m);
    for(int i=l;i<=r;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=1;k<=m;k++)a[j][k]=f[G[u][j-1]][i+k];
        }
        f[u][i]=c[u]*(d[u]-i)*(d[u]-i)+match(m);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int r;
        cin>>c[i]>>d[i]>>r;
        G[r].push_back(i);
    }
    dfs(0,0,0);
    cout<<f[0][0]<<'\n';
    return 0;
}