[CF773D]Perishable Roads

CF773D]Perishable Roads"/>

[CF773D]Perishable Roads

[CF773D]Perishable Roads

题目大意：

一个\(n(n\le2000)\)个点的完全图\(G\)，定义\(d(x)\)为生成树上点\(x\)到根路径上的最小边权。问图\(G\)的生成树\(\sum d(x)\)最小是多少？

思路：

由题解得到图的一些性质，然后就不难了。

源代码：

#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
using int64=long long;
inline int getint() {register char ch;while(!isdigit(ch=getchar()));register int x=ch^'0';while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');return x;
}
constexpr int N=2001;
bool vis[N];
int w[N][N],d[N];
int main() {const int n=getint();int min=INT_MAX;for(register int i=1;i<=n;i++) {for(register int j=i+1;j<=n;j++) {min=std::min(min,w[i][j]=w[j][i]=getint());}}d[0]=INT_MAX;for(register int i=1;i<=n;i++) {d[i]=INT_MAX;for(register int j=1;j<=n;j++) {if(i==j) continue;w[i][j]-=min;d[i]=std::min(d[i],w[i][j]*2);}}for(register int i=1;i<=n;i++) {int k=0;for(register int j=1;j<=n;j++) {if(!vis[j]&&d[j]<d[k]) k=j;}vis[k]=true;for(register int j=1;j<=n;j++) {d[j]=std::min(d[j],d[k]+w[k][j]);}}for(register int i=1;i<=n;i++) {printf("%lld\n",(int64)min*(n-1)+d[i]);}return 0;
}

转载于:.html