自动搬运

查看原文

来自洛谷，原作者为

	FQ04gty Let me be cruel, not unnatural.

搬运于2025-08-24 22:19:34，当前版本为作者最后更新于2022-10-19 21:37:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

首先，本题并不需要 DP。

考虑一个城市作为粮仓时可以使多少城市无需作为粮仓。

建出图的 Kruskal 重构树，倍增地找到深度最浅的，且权值不大于第 $i$ 个城市运粮车油量的点 $loc_i$（在原图中是边）。

可以发现，让父亲作为粮仓，一定比让儿子作为粮仓优——可以覆盖更多节点。

记 $cnt_i$ 为重构树中 $i$ 节点是几个叶子倍增找到的权值最大点。

因此，只需要从根节点开始 dfs，遇到最近的满足 $cnt_i>0$ 的节点将答案增加 $1$ 并返回。这样就得出了第一个答案 $ans$。

该部分时间复杂度 $O(n\log n)$。

考虑统计每个节点不作为粮仓时的答案。

可以发现：

• 当 $loc_i$ 不属于刚才 dfs 出的点集时，答案为 $ans$。

• 否则，当 $cnt_{loc_i}>1$ 时，只需要把粮仓换成相同效果的另一个点，答案依然为 $ans$。

• 否则，当 $cnt_{loc_i}=1$ 时，我们按照刚刚从根节点开始的 dfs 方式从 $loc_i$ 开始 dfs，统计新增的点数 $k$，答案为 $ans+k-1$。需要注意的是，如果 dfs 到了 $i$，则无法将粮食运到 $i$，输出 $-1$。

分析时间复杂度：

前两种情况单次都是 $O(1)$ 的。

后一种情况，考虑重构树被若干个 $cnt_i>0$ 的点分隔成若干个连通块，每次只会访问到其中一个。总共访问的点数是 $O(n)$ 级别的。

因此，该算法总时间复杂度为 $O(n\log n)$。

Code

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int SIZE=6e5+10,BIT=25,inf=0x3f3f3f3f;
inline int read()
{
    int x=0,opr=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')opr=-opr;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x*10)+(ch^48),ch=getchar();
    return x*opr;
}
vector<int>son[SIZE];
int n,m,f[SIZE],val[SIZE],sizep,fa[SIZE][BIT],maxv[SIZE][BIT],g[SIZE],cnt[SIZE],loc[SIZE],ans;
bool need[SIZE];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
struct edge{int u,v,w;inline void build(){u=read(),v=read(),w=read();};inline bool operator<(edge x){return w<x.w;}}e[SIZE];
void dfs(int thisp)
{
    for(int i=1;i<BIT;i++)fa[thisp][i]=fa[fa[thisp][i-1]][i-1],maxv[thisp][i]=max(maxv[thisp][i-1],maxv[fa[thisp][i-1]][i-1]);
    for(int nxt:son[thisp])dfs(nxt);
}
int tot;
inline int get(int x){int G=g[x];for(int i=BIT-1;~i;i--)if(maxv[x][i]<=G)x=fa[x][i];return x;}
int solve(int thisp){if(cnt[thisp]||thisp<=n)return tot++,need[thisp]=1;int res=0;for(int nxt:son[thisp])res+=solve(nxt);return res;}
int test(int thisp,int from){if(thisp==from)return SIZE;if(cnt[thisp]&&thisp!=loc[from]||thisp<=n)return 1;int res=0;for(int nxt:son[thisp])res+=test(nxt,from);return res;}
int main()
{
    sizep=n=read(),m=read();
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)e[i].build();
    for(int i=1;i<=n;i++)g[i]=read();
    sort(e+1,e+m+1);
    for(int i=1,u,v;i<=m;i++)
    {
        u=find(e[i].u),v=find(e[i].v);
        if(u==v)continue;
        val[++sizep]=e[i].w,maxv[u][0]=maxv[v][0]=e[i].w,fa[u][0]=fa[v][0]=f[u]=f[v]=f[sizep]=sizep,son[sizep].push_back(u),son[sizep].push_back(v);
    }
    maxv[sizep][0]=inf,dfs(sizep);
    for(int i=1;i<=n;i++)cnt[loc[i]=get(i)]++;
    printf("%d ",ans=solve(sizep));
    for(int i=1,res;i<=n;i++)
    {
        if(cnt[loc[i]]>1||!need[loc[i]]){printf("%d ",ans);continue;}
        res=ans-1+test(loc[i],i);
        printf("%d ",res>=SIZE?-1:res);
    }
    return 0;
}