D. Perishable Roads

題意簡(jiǎn)述： 一個(gè) $n$ 個(gè)點(diǎn)的完全圖 以 $i$ 為根節(jié)點(diǎn)時(shí)

詢問 能構(gòu)造的樹的 $\sum d(x)$ 最小是多少。

$d(x)$： $x$ 到根節(jié)點(diǎn)邊權(quán)值最小值

MOONPIE題解

---

首先有一個(gè)顯而易見的錯(cuò)誤貪心：

不妨假設(shè)以$\text{root}$為根節(jié)點(diǎn)重構(gòu)樹，定義$u\to v$這條路徑是所有路徑的最小值，則我們肯定希望這樣構(gòu)造路徑：
$$\text{root}\to u\to v?\text{others}$$
也就是把其他所有點(diǎn)都往$v$上連（構(gòu)成一棵樹），這樣其他點(diǎn)的代價(jià)都是$w_{u\to v}$，不難得出所求為$w_{\text{root}\to u}+(n?2)\times w_{u\to v}$。
容易想到反例也就是如果$w_{\text{root}\to u}$非常非常大，則會(huì)不是最優(yōu)值！！！

不過(guò)我們只需要找到一條路徑$\text{root}?u$ 代替$\text{root}\to u$，不難想到答案一定是這種情況：$\text{root}?u\to v?\text{others}$（其中$\text{root}?u$是一條鏈而$v?\text{others}$是一棵樹）

---

對(duì)于鏈上路徑的值有一個(gè)結(jié)論（詳細(xì)可查看RingweEH）：

$\text{root}\to ?\to i\to j\to k\to u\to v$
這條鏈上的邊權(quán)一定單調(diào)遞減且只可能存在一例例外（即有可能$w_{i\to j}\le w_{k\to u}$）

對(duì)于計(jì)算答案來(lái)說(shuō)，樹上的點(diǎn)$v?\text{others}$對(duì)答案的貢獻(xiàn)是$(n?1?x)\times w_{u\to v}$而鏈上的點(diǎn)由于單調(diào)遞減，只需要從$\text{root}$跑一邊最短路即可由于不知道鏈上邊的個(gè)數(shù)$x$只需要利用花費(fèi)提前的思想，跑最短路前把每條邊減去$w_{u\to v}$即可，對(duì)于例外情況特殊考慮一下即可。

#include<cstring> #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr int N=2010; int g[N][N],n; ll d[N]; bool st[N]; void dijkstra(int S) {memset(d,0x3f,sizeof d);memset(st,0,sizeof st);d[S]=0;for(int i=1;i<=n;i++)//例外for(int j=1;j<=n;j++)d[i]=min(d[i],g[i][j]*2ll);for(int i=1;i<=n;i++){int t=-1;for(int j=1;j<=n;j++)if(!st[j]&&(t==-1||d[t]>d[j])) t=j;st[t]=1;for(int j=1;j<=n;j++) d[j]=min(d[j],d[t]+g[t][j]);} }int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;int S=1,mn=0x3f3f3f3f;memset(g,0x3f,sizeof g);for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){cin>>g[i][j];g[j][i]=g[i][j];if(mn>g[i][j]) mn=g[i][j],S=i;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) g[i][j]-=mn;dijkstra(S); for(int i=1;i<=n;i++) cout<<1ll*(n-1)*mn+d[i]<<'\n'; }

要加油哦~

總結(jié)

以上是生活随笔為你收集整理的codeforces773 D. Perishable Roads（思维+最短路）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。