「Wdsr-1」仓库建设

RED12956 · 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;
}