P9341 [JOISC 2023 Day4] Security Guard Sol

syf2008 · 2023-05-24 13:55:15 · 题解

本文部分是参考 djwj233 的 sol 写的，加入了自己的理解。

简要题意：

给定一张 N 个点 M 条边的图，每条边上都有一艘船。每个点有权值 S_i。最开始的时候，你可以给每艘船一个权值，权值可以在端点（即中转点）间自由转移。

但是你需要保证对于所有时刻所有停靠在端点上的船，都有：

该船上的权值不小于停靠的点的权值。

你想要任意两点可以通过船相互可达权值总和的最小值。

对于给定的 Q，可能会最多增加 Q 条边（增加位置的两端任意）你需要对于所有 x \in N \cap [0,Q] 都求出答案。

前置：T 为边集，S_i 为点权。

Sub1:

Sub1 是简单的，因为 S_i\le 2，所以只有 2 种权值。

对于权值为 1 的点，我们可以先给每条边赋上 \max(S_u,S_v)，然后可以调整，如果对于一个 S_i-S_{i+1}=1 的边，我们可以通过把其中一条边的边权降为 1，因为船上的权值可以转移。

code:

namespace sub1
{
    int ans=0;
    void main()
    {
        for(int i=2;i<=n;i++)ans+=max(a[i-1],a[i]);
        for(int i=1;i<n-1;i++)ans-=max(0ll,a[i]-a[i+1]);
        cout<<ans<<'\n';
    }
}

Sub2：

首先对于树有个推论：

就是对于每条边，记船上的权值为 x。

\min(S_u,S_v)\le x \le \max(S_u,S_v)

下界：如果 x < \min(S_u,S_v)，那么这个船无法移动到相邻的 2 个节点的任何一个，相当于这条边就废了，对于树就有节点不能两两可达。

上界：可以向左或向右移动一定权值得到一组不劣的解。

考虑这是个链，合法的必要条件是我们可以从 1 走到 n。

这个过程一定可以被调整为：

进行若干步从右向左的移动，把多余的权值转移到人
最后一次性地从 1 一直向右走到 n。

移动是可逆的，所以现在我们对于任意一种合法的情况，进行第一步操作，这样可以得到一种合法情况，使得所有船都在左边。

因此，一定存在一组最优解使得所有船都在左边。

保证了这一点后我们可以从左往右贪心构造出一组最小解，满足 1 可达 n，同时它也是合法的：

对于路径 x\to y，若 x<y，那么我们可以直接 1\to n 的方案，钦定 x 处上客，y 处下乘客；
由于所有操作可逆，所以我们可以反着构造出 n \to 1 的解，类似的 x>y 的也均合法。

code:

namespace sub2
{
    int ans=0;
    void main()
    {
        for(int i=2;i<n;i++)ans+=a[i];
        cout<<ans+*max_element(a+1,a+n+1);
    }
}

Sub3：

考虑一棵树怎么做。

根据上面内容的启发,我们可以定一个根 rt。

对于每条边 (fa_x,x)，船都在 fa_x 上。且从 rt 到每个点的过程都是直接不断向下走。

证明类似于链，请自证。

可以对于每个根都试一遍，复杂度 O(n^2)，无法通过。

我们直接钦定根为 S_i 最大的一个。这样我们对于每条边 (fa_x,x)，直接取边权为 S_{fa_x} 一定合法。

证明：

我们设根为 rt，每个点 x 的度数为 deg_x，用 V 表示这个贡献。

贡献总和为 \sum_{x=1}^{n}S_x \times (deg_x-1)+S_{rt}。

如果根是 x，贡献变为 V-S_x \times (deg_x-1)+rt \times deg_x。

可以发现根位于 S_x 最大的位置时贡献最小，证毕。

code:

namespace sub3
{
    int dfs(int x,int fa)
    {
        int res=0;
        for(auto y:e[x])if(y!=fa){res+=a[x]+dfs(y,x);}
        return res;
    }
    int rt=1;
    void main()
    {
        for(int i=2;i<=n;i++)if(a[rt]<a[i])rt=i;
        cout<<dfs(rt,0)<<'\n';
    }
}

sub4：

发现和 sub3 相比，就是多了一些可选的边。

然后不难想到，就是删除一些边，然后依旧是构成一颗树，用 sub3 做就行了。

考虑扣树，可以想到最小生成树。

这样问题就被转化为：

找一棵以 rt 为根的有根树，使得 \sum_{x=1}^{n}S_x \times (deg_x-1)+S_{rt} 权值最小。

先去拆一下贡献，把点的贡献摊到边上，不难得到：

S_{rt}- \sum_{x=1}^{n}S_x + \sum_{(u,v) \in T}^{}(S_u+S_v)

前半部分为定值，后半部分就是一个子问题：

给定原图的每条边 (u,v)，边权为 S_u+S_v，求最小生成树。

~~这个相信大家都会~~。

code：

namespace sub4
{
    struct edge{int x,y,z;}ee[N<<1];int len;
    int fa[N];
    int afind(int x){return fa[x]==x?x:fa[x]=afind(fa[x]);}
    int ans,xx,yy;
    void main()
    {
        ans=*max_element(a+1,a+n+1)-accumulate(a+1,a+n+1,0);
        iota(fa+1,fa+n+1,1);
        for(int x=1;x<=n;x++)
        for(auto y:e[x])if(x<y)
        ee[++len]=(edge){x,y,a[x]+a[y]};
        sort(ee+1,ee+len+1,[](const edge&a,const edge&b){return a.z<b.z;});
        for(int i=1;i<=len;i++)
        {
            xx=afind(ee[i].x);yy=afind(ee[i].y);
            if(xx!=yy){fa[xx]=yy;ans+=ee[i].z;}
        }
        cout<<ans<<'\n';
    }
}

sub5+6：

现在可以加边了，我们考虑这个过程：

如果是一张图，必定是先抠出一颗最小生成树。

加边必然是从最小生成树上断掉一条边再加上一条边。

断掉边 (u,v) 后，我们要找到断边之后 u 和 v 所在的两个连通块内 S_i 最小的两个点相连。

设 p 是全局 S_i 最小的点，可以发现，重新连边的过程中，一定有一个端点是 p，所以最多只有 n-1 条边可能被加入。

这样我们可以 O(2^n) 枚举有哪些边被加入。

事实上，我们由上面的过程可以证明 k=m+1 中断的边一定包含 k=m 中断的边，所以直接暴力模拟上面的过程，O(n) 枚举菊花边，再 O(n) 枚举原树边中要拆掉的边，就是 O(n^2) 的。

code：

namespace sub56
{
    int minn[N];
    int sum[N];
    struct edge{int x,y,z;}ee[N<<2];int len;
    struct edges{int y,z;};
    vector<edges>eee[N];
    int fx,fy,fz,val[N];
    int rt,fa[N];
    int dfsmax(int x,int dad)
    {
        minn[x]=x;
        for(auto [y,z]:eee[x])
        if(y!=dad)
        {
            int temp=dfsmax(y,x);
            if(a[minn[x]]>a[temp])
            minn[x]=temp;
        }
        return minn[x];
    }
    void dfs(int x,int dad)
    {
        if(val[x]&&(a[rt]+a[minn[x]])-val[x]<fz){fz=(a[rt]+a[minn[x]])-val[x];fy=minn[x];fx=x;}
        for(auto [y,z]:eee[x])
        if(y!=dad)
        {
            fa[y]=x;val[y]=z;
            dfs(y,x);
        }
    }
    int afind(int x){return fa[x]==x?x:fa[x]=afind(fa[x]);}
    int ans,xx,yy;
    void main()
    {
        sum[0]=*max_element(a+1,a+n+1);
        for(int i=1;i<=n;i++)sum[0]-=a[i];
        rt=min_element(a+1,a+n+1)-a;
        iota(fa+1,fa+n+1,1);
        for(int x=1;x<=n;x++)
        for(auto y:e[x])
        ee[++len]=(edge){x,y,a[x]+a[y]};
        sort(ee+1,ee+len+1,[](const edge&a,const edge&b){return a.z<b.z;});
        for(int i=1;i<=len;i++)
        {
            xx=afind(ee[i].x);yy=afind(ee[i].y);
            if(xx!=yy)
            {
                fa[xx]=yy;
                sum[0]+=ee[i].z;
                eee[ee[i].x].emplace_back((edges){ee[i].y,ee[i].z});
                eee[ee[i].y].emplace_back((edges){ee[i].x,ee[i].z});
            }
        }
        memset(fa,0,sizeof(fa));
        for(int p=0;;p++)
        {
            dfsmax(rt,0);
            fz=0;dfs(rt,0);
            if(fz==0)break;
            sum[p+1]=sum[p]+fz;
            for(auto it=eee[fx].begin();it!=eee[fx].end();it++)
            if(it->y==fa[fx]){eee[fx].erase(it);break;}
            for(auto it=eee[fa[fx]].begin();it!=eee[fa[fx]].end();it++)
            if(it->y==fx){eee[fa[fx]].erase(it);break;}
            eee[fy].emplace_back((edges){rt,a[rt]+a[fy]});
            eee[rt].emplace_back((edges){fy,a[rt]+a[fy]});
        }
        for(int i=0;i<=q;i++)if(!sum[i])sum[i]=sum[i-1];
        for(int i=0;i<=q;i++)cout<<sum[i]<<'\n';
    }
}

sub7：

最妙的一档，考虑时间倒流，最终，整张图是一张以最小的点为花心的菊花图，之后就是断掉菊花上的边，选择原来存在的一条边替换。

我们把菊花上的人为加上去的边看作虚边，这样所有实边形成的连通块之后不会分开，可以用并查集维护。

每次的操作是选择两个连通块，把其中一个的虚边断掉，用两连通块内的边把它们连到一起。

考虑对每个连通块，维护把这条虚边断掉至少要多少的代价。只要维护出这个代价就可以了。

这个东西等价于从连通块内连向连通块外的边的边权和减去连通块内的点的点权加上根的点权，后面根的点权不用维护，重点是前面的东西的合并怎么处理。

这个东西可以用可并堆维护，每次弹出堆顶的不合法边即可，总复杂度 O(n \log n)，如果使用启发式合并是 O(n \log^2 n)。

code：

namespace sub7
{
    #define mk make_pair
    #define fi first
    #define se second
    int sum[N],ans;
    int rt,fa[N];
    int afind(int x){return fa[x]==x?x:fa[x]=afind(fa[x]);}
    set<pair<int,int>>S;
    __gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int> > >qq[N];
    struct edge{int x,y,z;}ee[N<<2];int len;
    int calc(int x){return qq[x].top().fi-(a[rt]+a[x]);}
    void merge(int x,int y)
    {
        S.erase(mk(calc(x),x));S.erase(mk(calc(y),y));
        fa[x]=y;qq[y].join(qq[x]);
        while(qq[y].size()&&afind(qq[y].top().se)==y)qq[y].pop();
        if(qq[y].size())S.insert(mk(calc(y),y));
    }
    void main()
    {
        ans=*max_element(a+1,a+n+1);
        for(int i=1;i<=n;i++)ans-=a[i];
        rt=1;for(int i=1;i<=n;i++)if(a[i]<a[rt])rt=i;
        for(int i=1;i<=n;i++)if(rt!=i)sum[n-1]+=a[rt]+a[i];
        for(int x=1;x<=n;x++)
        for(auto y:e[x])
        ee[++len]=(edge){x,y,a[x]+a[y]};
        for(int i=1;i<=len;i++)qq[ee[i].x].push(mk(ee[i].z,ee[i].y));
        for(int i=1;i<=n;i++)fa[i]=i,S.insert(mk(calc(i),i));
        for(int now=n-1;S.size();)
        {
            int x=S.begin()->se;
            sum[now-1]=sum[now]+calc(x);now--;
            merge(x,afind(qq[x].top().se));
        }
        for(int i=0;i<=q;i++)cout<<sum[min(i,n-1)]+ans<<'\n';
    }
    #undef mk
    #undef fi
    #undef se
}

~~完整代码就不放了~~。