网站超级推广,谁做的12306网站,企业建站系统开源,农村网站做移动D. Perishable Roads 题意简述#xff1a; 一个 nnn 个点的完全图 以 iii 为根节点时 询问 能构造的树的 ∑d(x)\sum d(x)∑d(x) 最小是多少。 d(x)d(x)d(x)#xff1a; xxx 到根节点边权值最小值 MOONPIE题解 首先有一个显而易见的错误贪心#xff1a;
不妨假设以root\t…D. Perishable Roads 题意简述 一个 nnn 个点的完全图 以 iii 为根节点时 询问 能构造的树的 ∑d(x)\sum d(x)∑d(x) 最小是多少。 d(x)d(x)d(x) xxx 到根节点边权值最小值 MOONPIE题解 首先有一个显而易见的错误贪心
不妨假设以root\text{root}root为根节点重构树定义u→vu\to vu→v这条路径是所有路径的最小值则我们肯定希望这样构造路径 root→u→v⇝others\text{root}\to u\to v\leadsto \text{others}root→u→v⇝others 也就是把其他所有点都往vvv上连构成一棵树这样其他点的代价都是wu→vw_{u\to v}wu→v不难得出所求为wroot→u(n−2)×wu→vw_{\text{root}\to u}(n-2)×w_{u\to v}wroot→u(n−2)×wu→v。 容易想到反例也就是如果wroot→uw_{\text{root}\to u}wroot→u非常非常大则会不是最优值
不过我们只需要找到一条路径root⇝u\text{root}\leadsto uroot⇝u 代替root→u\text{root}\to uroot→u不难想到答案一定是这种情况root⇝u→v⇝others\text{root}\leadsto u\to v\leadsto \text{others}root⇝u→v⇝others其中root⇝u\text{root}\leadsto uroot⇝u是一条链而v⇝othersv\leadsto \text{others}v⇝others是一棵树 对于链上路径的值有一个结论详细可查看RingweEH
root→⋯→i→j→k→u→v\text{root}\to\dots\to i\to {j}\to k\to u\to vroot→⋯→i→j→k→u→v 这条链上的边权一定单调递减且只可能存在一例例外即有可能wi→j≤wk→uw_{i\to j}\leq w_{k\to u}wi→j≤wk→u
对于计算答案来说树上的点v⇝othersv\leadsto \text{others}v⇝others对答案的贡献是(n−1−x)×wu→v(n-1-x)×w_{u\to v}(n−1−x)×wu→v而链上的点由于单调递减只需要从root\text{root}root跑一边最短路即可由于不知道链上边的个数xxx只需要利用花费提前的思想跑最短路前把每条边减去wu→vw_{u\to v}wu→v即可对于例外情况特殊考虑一下即可。
#includecstring
#includeiostream
#includealgorithm
using namespace std;
using lllong long;
constexpr int N2010;
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 i1;in;i)//例外for(int j1;jn;j)d[i]min(d[i],g[i][j]*2ll);for(int i1;in;i){int t-1;for(int j1;jn;j)if(!st[j](t-1||d[t]d[j])) tj;st[t]1;for(int j1;jn;j) d[j]min(d[j],d[t]g[t][j]);}
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;int S1,mn0x3f3f3f3f;memset(g,0x3f,sizeof g);for(int i1;in;i)for(int ji1;jn;j){cing[i][j];g[j][i]g[i][j];if(mng[i][j]) mng[i][j],Si;}for(int i1;in;i)for(int j1;jn;j) g[i][j]-mn;dijkstra(S); for(int i1;in;i) cout1ll*(n-1)*mnd[i]\n;
}要加油哦~
