CF773D Perishable Roads
思路：注意到答案应该是链加上一串贡献相同的树的贡献，因为若 \(a \to u\) 的贡献 比 \(b \to u\) 的贡献小，那么可以连 \(b \to a\)，答案会更优。
那么有一个贪心思路，对于每个根，找到连向这个根的最短边，然后对于这条边的另一个端点，也找到连向这个端点的最短边，以此类推；很显然，这个假了。
设 \(T\) 为当前根，思量找到全局最短边 \((u,v,w)\)，思量令 \(u \to T\)，然后其它所有点都连 \(v\)，这样其它点到 \(T\) 的贡献必然是最小的，但是若 \(u \to T\) 的贡献非常大，那这样也是不优的。
则思量构成一个 \(u \to T\) 的一条链，使得这条链的贡献加上其它所有点的贡献最优，设 \(d_T\) 表示从 \(u\) 到 \(T\) 构成的链的贡献的最小值，\(x\) 为 \(u \to T\) 除 \(T\) 以外的点的个数。
则贡献为 \(d_T + (n-x-1) w\)，发现这个 \(x\) 很烦，思量去掉，即我们盘算 \(d\) 的时间，对于全局边都减去一个 \(w\)，则 \(d_T' = d_T - x \times w\) 了。
此时贡献为 \(d_T + (n-1)w\)，则我们要求出 \(d_T\) 的最小值，发现是个单源最短路问题，直接跑 dijkstra 即可。
时间复杂度为 \(O(N^2)\)。
完备代码：
#include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(register int i=l;i=l;i--)using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=2020,INF=1e18;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c
页:
[1]