CF773D
lsj2009
·
·
题解
Description
给定一个 n 个点的完全图 \mathcal{G}(V,E)，边带权。
我们定义其一个生成树 \mathcal{T}(V'=V,E'\subseteq E) 的权值是：
- 我们认为一个点 u 的权值树上根到 u 路径上边权的最小值。
- 我们认为树 \mathcal{T} 的权值是所有节点权值之和。
请对于每一个节点 u\in V 求出所有以他为根的生成树中权值的最小值。
## Solution
闲话：
这真的是 2700 吗？？？
机房三个人想了 1h+ 都没做出来，汗流浃背了/dk/dk/dk
（虽然可能当时想得差不多了，但是没有完全做出来就是了。）
### Observation 1
我们尝试观察最终树 $\mathcal{T}$ 的形态，通过直觉下面结论：
- 树 $\mathcal{T}$ 一定**形如一种「扫把」的形态**，也就是 **链 + 菊花**，大概如下：
约定：
1. 我们称下半部分为「**菊花**」。
2. 我们称菊花与链衔接的那条边（在上图中为 $(3,4)$）为「**把颈**」。
4. 在链上除去把颈的其于部分为「**把柄**」。
证明：
- 首先来证明**下半部分必然为菊花**：如果不为菊花，必然存在若干个儿子会继续向下拓展延申出去，我们**逐个考虑每个不合法的儿子**，进行调整；则对于每个儿子：
- 如果下方延申出去的边存在某个小于我的「把颈」，那不妨令那条边成为我新的「把颈」，如下：
- 
- 也就是 $w(5,8)<w(3,4)$。容易发现我这样调整权值必然不劣。
- 如果我这个儿子下面是条链那就没了；否则如果下面也形如一棵多叉树那么我考虑逐层**从下往上归纳调整**即可。
- 如果下方延申出去的边均大于我的「把颈」，那我将下面所有的点直接挂到「把颈」上即可。
- 其实就是把上面的调整反一下，容易发现这样调整权值不变。
- 再来考虑说明上半部分必然是一条链：
- 我们考虑找出生成树 $\mathcal{T}$ 的最小边 $(u,v)$（设 $u$ 是 $v$ 父亲，其实也就是我们的「把颈」），然后取出其到根的路径 $\mathcal{P}=\text{root}\to u$ 和 $v$ 的子树 $\mathcal{T'}$，则我们将不在 $\mathcal{P}\cup\mathcal{T'}$ 上的点全部挂到「把颈」下即可：
- 
- 其中 $\min{w}=w(3,4)$；容易发现这样操作权值必然不劣。
- 此时虽然下半部分不满足是菊花图，但其实我们按照上面对于菊花图的处理进行调整即可。
这样子我们给出了证明：$\mathcal{T}$ 的形态必然是一个「扫把」。
### Observation 2
更进一步的，我们可以说明：**「把颈」必然是全局最小边**（如有多个则任意一个均可）。
反证：
- 设 $\min{w}=w(u,v)$。如果不是，则把颈为某条边 $(u',v')$，则考虑如下方案：
- 我们考虑「把柄」部分不变，「菊花」部分连边：$(v',u),(u,v)$，这显然比我们将 $u,v$ 都挂在 $v'$ 下面优秀，然而这和我们前面说明的 **下部分必然是菊花图** 矛盾了。
- 当然这里有一个特殊情况是：如果 $u/v$ 在「把柄」中出现过了咋办？？？这并不会有。因为你都在把柄中遇到 $\min{w}=w(u,v)$ 了，那让他成为「把颈」岂不会更优？？
### Observation 3
另一个结论：「把柄」部分除去最后一条边之外**从上往下权值单调不增**。
证明：
- 如果我们出现这样一种情况：
- 
- 同样考虑调整：
- 
- 因为我们注意到无论如何我们都有 $\Delta=\operatorname{value}(3)=\operatorname{value'}(5)=w(1,2)$ 对答案额外产生的贡献（显然期望情况下就是节点权值递减）（然而第二个等号其实也不一定成立，因为 $w(2,5)$ 的权值是 ？，也就是我们并不关心其具体权值，虽然其有可能小于 $w(1,2)$，但对我们证明没有影响），那我不妨直接令其于节点直接获得 $\min{w}$ 的权值，这陷入不劣！
- 注意还有一种特殊情况：我们无法保证 $w(2,5)<w(1,2)$！
- 这也就是最开始说的，**除去最后一条边之外**从上往下权值单调不增。
### Full solution
根据 Observation 1~3 我们尝试推导出完整做法（设 $\min{w}=(u,v)$）：
1. 对于 $\text{root}=u/v$ 我们显然有 $\text{answer}=(n-1)\min{w}$。
2. 否则考虑从 $u/v$ 向上拓展到 $\text{root}$。具体的，考虑 Observation 1~2，观察「扫把」的形状，我们每次从「菊花」中拉出一个点 $x$ 让他成为 $\text{root}$，也就是在「把柄」的最上端加入一个点。
- 考虑答案的变化：显然这时候 $x$ 不再对答案产生贡献，所以 $\text{answer}\gets \text{answer}-\min{w}$，但是注意到「把柄」上的点对答案贡献会产生变化：
- 考察加入 $x$ 前的 $\text{root}=y$，则 $y$ 显然会新加贡献 $w(x,y)$。
- 考虑 Observation 3，由于「把柄」上满足**从上往下权值单调不增**，所以 $w(x,y)$ 不会对其于「把柄」上的点权产生影响。
- 所以 $\text{answer}$ 变化为：$\text{answer}\gets \text{answer}+(w(x,y)-\min{w})$。
3. 注意到我对 $\Delta\text{answer}$ 的写法了吗！我们考虑建新图 $\mathcal{G'}(V'=V,E'=\{(x,y,w(x,y)-\min{w})|(x,y)\in E\})$，对其跑关于 $u/v$ 的最短路即可！！！
- 这种做法在几点上形成了惊人的自洽：
- 注意到我们有 $w(x,y)\ge \min{w}$，所以在新图上边权非负，我们可以直接跑 Dijkstra！而根据 Dijkstra 的特性，**我们跑出来的图必然是一个 DAG（即最短路 DAG）**，所以从 $u/v\to x$ 的一条路径**必然是简单路径**，也就是「把柄」！
- 我们有 $w'(u,v)=0$，所以无论是从 $u$ 还是 $v$ 开始跑都可以得到相同的结果！
4. 然而其实还有一个不太优雅的 corner case：
- 我们的 Observation 3 有一个小 case：**除去最后一条边之外**从上往下权值单调不增。
- 也就是其实「$w(x,y)$ 不会对其于「把柄」上的点权产生影响」不完全正确。
- 处理是简单的，我们考虑「把柄」上倒数第二条边，他会对答案有**两次**的贡献，在初始化时设置即可，具体详见代码。
复杂度 $\mathcal{O}(n^2)$。
## Code
```cpp
#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
#define int long long
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
// system("fc .out .ans");
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
bool M1;
const int N=2e3+5;
int g[N][N],dis[N],n;
bool used[N];
void dijkstra(int st) {
cl(dis,0x3f);
rep(i,1,n) {
dis[i]=g[st][i];
rep(j,1,n)
chkmin(dis[i],g[i][j]*2);
}
rep(_,1,n) {
int k=0;
rep(i,1,n) {
if(!used[i]&&dis[i]<dis[k])
k=i;
}
if(!k)
continue;
used[k]=true;
rep(i,1,n) {
if(!used[i]&&dis[i]>dis[k]+g[k][i])
dis[i]=dis[k]+g[k][i];
}
}
}
void solve() {
cl(g,0x3f);
scanf("%lld",&n);
int mn=INFLL,p=0;
rep(i,1,n) {
rep(j,i+1,n) {
int x;
scanf("%lld",&x);
g[i][j]=g[j][i]=x;
if(mn>x) {
mn=x;
p=i;
}
}
}
rep(i,1,n) {
rep(j,1,n)
g[i][j]-=mn;
}
dijkstra(p);
rep(i,1,n)
printf("%lld\n",dis[i]+(n-1)*mn);
}
bool M2;
signed main() {
//file_IO();
int testcase=1;
//scanf("%d",&testcase);
while(testcase--)
solve();
fprintf(stderr,"used time = %ldms\n",1000*clock()/CLOCKS_PER_SEC);
fprintf(stderr,"used memory = %lldMB\n",(&M2-&M1)/1024/1024);
return 0;
}
```