Codeforces 806 D. Perishable Roads Dijkstra

编程入门 行业动态 更新时间:2024-10-09 21:22:59

<a href=https://www.elefans.com/category/jswz/34/1770097.html style=Codeforces 806 D. Perishable Roads Dijkstra"/>

Codeforces 806 D. Perishable Roads Dijkstra

原文链接.html

题目传送门 - CF806D

题意

  给定一个 n 个点的无向完全图,每一条边有一定的边权。

  对于它的一个生成树,我们定义一个节点的花费为该点到根的边权min 。

  一个生成树的权值为所有节点的花费之和。

  对于每一个节点,求出以他为根的最小生成树权值。

  $n\leq 2000$

题解

  首先,我们考虑找出权值最小的边。

  那么,一旦这条边被连到了根,剩下的所有点直接连向它就好了。

  假设有一个根,那么最优解之一 一定长成这样:

  其中根为最上面那个点,黑色点的上面直接连接的边权值为 min 。

  我们将所有点的权值先减掉min 。

  这之后我们只需要求出“将根和任意一个连接 0 边的节点连通的最小花费”即可。

  

  考虑将从黑色节点到根的边权依次写出来,假设是 $w_1,w_2,w_3,\cdots ,w_n$ ,那么有这样一个性质:

  最优解之一 一定满足 $\forall i>1, w_i<w_{i+1}$ 。

  因为如果存在一个不满足的 $i$ ,我们可以直接把第 $i-1$ 个接上去,把第 $i$ 个接到黑点上面。

  对于第一条边,当然不需要满足。

 

  设一个超级源点 S ,使他免费连向所有与 0 边直接相连的点,并与其他点没有边。

  于是,对于任何一个点 x,对于它连向的任意一个与 0 边直接相连的点 y ,将 d[x][S] 变成 min(d[x][S],2*d[x][y]) 即可。

 

  最后只要从 S 开始跑一下最短路就好了。

 

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read(){LL x=0,f=0;char ch=getchar();while (!isdigit(ch))f|=ch=='-',ch=getchar();while (isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return f?-x:x;
}
const int N=2005;
const int INF=2e9;
int n;
int g[N][N];
int tag[N],near[N];
int vis[N];
LL dis[N];
int main(){n=read();int Min=INF;for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++){g[i][j]=g[j][i]=read();Min=min(Min,g[i][j]);}for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (i!=j){g[i][j]-=Min;if (!g[i][j])tag[i]=tag[j]=1;}int S=n+1;for (int i=1;i<=n;i++)g[S][i]=g[i][S]=tag[i]?0:INF;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (i!=j){if (tag[i])near[j]=1;if (tag[j])near[i]=1;}for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (i!=j&&near[j])g[S][i]=g[i][S]=min(g[i][S],2*g[i][j]);for (int i=1;i<=n+1;i++)vis[i]=0,dis[i]=1e15;dis[S]=0;for (int i=1;i<=n+1;i++){int x=0;for (int j=1;j<=n+1;j++)if (!vis[j]&&(x==0||dis[j]<dis[x]))x=j;vis[x]=1;for (int j=1;j<=n+1;j++)if (!vis[j]&&dis[j]>dis[x]+g[x][j])dis[j]=dis[x]+g[x][j];}for (int i=1;i<=n;i++)cout << dis[i]+(LL)Min*(n-1) << endl;return 0;
}

  

 

转载于:.html

更多推荐

Codeforces 806 D. Perishable Roads Dijkstra

本文发布于:2024-03-13 00:51:30,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1732812.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:Codeforces   Perishable   Dijkstra   Roads

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!