题意
给出n个点完全图，边有边权。枚举x=1~n，找出一棵以x为根的生成树，定义每个点到根的距离di为到根路径上最小的边权，生成树的花费为
∑di
∑
d
i
。对于每个x，找出最小花费。 n<=2000
前言
早上男神出的比赛的。。 当时没有做出来。。 但是感觉连
n3
n
3
的分都没拿到真是耻辱啊TAT
反思放前面
①还是要相信自己的想法吧，要不断地把自己的想法挖深 ②一定要看准部分分，虽然一直想不到
n2
n
2
的做法，但是
n3
n
3
也是一定要尝试去想的，适当地降低标准往往可以拿到更高的分数 ③如果看见，每多选一个就会损失一些代价，那么往往可以直接在原来的代价上减去这个代价 ④比赛一定要大胆猜结论。。
题解
下面分为两种做法，第一个是我一开始的方向，第二个是男神的方向
下文记所有边权的最小值是mn，所连出去的边权包含mn的叫做关键点
n^3的做法 ①
容易想到，最后答案肯定就是由i连出一堆边，然后连到一个最小值 然后后面就挂一个子树就可以了 那怎么知道连出一堆边是什么呢？ 我们假设，对于每一个点，他的代价都是mn 那么对于没有取到mn的点，假设他的值是x 那么他的代价就会变大
x−mn
x
−
m
n
我们可以对于所有边权减去mn 我们可以对于每个点跑一个最短路，终点是任意一个关键点 由于这是一个完全图，最短路是
n2
n
2
的 于是总体做法就是
n2
n
2
的 至于路径最小值 我们可以在DIJ的时候记录一下这个最短路的边权最小值，每一次比较一下就可以取小的了，其实不需要每一次取小，只需要在下一个是关键点的时候再比较就可以了，但是这样方便，在下文
n2
n
2
的做法可以证明这个做法的
我比较懒，因为这个代码不在这台电脑上，所以就不给了。。
n^2的做法①
考虑上面的做法，每一次都跑一次实在是太慢了 仔细观察的话，我们可以发现一个性质，那就是肯定存在一种方案，使得一开始选的边都是递减的，最后一个可能递增的就是下一个连接的点就是关键点 这个正确性还是很好证的啊，自己动动脑就好了 我们依然让边权减去mn 那么我们考虑一下，那么我们对于一个点i 我们一直走递减的边，走到j 我们可以知道，肯定有一条最短路
dis[i][j]
d
i
s
[
i
]
[
j
]
是可以满足这个条件的 然后，我们有两种操作，就是这个点就是关键点了，那么答案就是dis[i][j]，因为减去之后，这条边权已经是0了，所以加上最小边权g[i]，没有影响，为了方便，我们加上
dis[i][j]+g[j]∗2
d
i
s
[
i
]
[
j
]
+
g
[
j
]
∗
2
，为什么？下面就知道了 第二个操作，就是再走两条边走到关键点？那一条边的情况呢？因为如果下一条边是递减的，那么会在第一个情况枚举到。如果不是，那么边权就是要上一条边枚举到，就是这个了。容易知道，这个的答案就是
dis[i][j]+g[j]∗2
d
i
s
[
i
]
[
j
]
+
g
[
j
]
∗
2
但是这样还是
n3
n
3
的，怎么优化？ 这时候，我们可以从j开始，倒着往前跑，用dij来优化 那么就可以做到
n2
n
2
了
n^3的做法② la1la1la
还是先把所有边权减去mn 现在问题变成对每个点x，找出到标记的点的最短路，并且可以用先走的边权代替后走的边权。 不妨从标记点开始找，让后走的边权代替先走的边权。 一个朴素的想法是f[i][j]表示走到点i，有j条边要使用后面的边权的最短路。f[i][j]可以转移到f[k][0]或f[k][j+1] 容易知道这个DP的正确性 首先，他的答案肯定不会变小，其次，他肯定可以搜出正确答案 虽然过程的答案不一定是合法的，但是肯定可以搜出最后的答案 然而这个做法是
n3
n
3
的
n^3的做法② la1la1la
但是考虑做最短路的目的是找到一个标记点，走到很多个中间点显然不是什么好方案。具体来说，从i走j条边到k，只是为了使用最后一条边权(s,k)，那为什么不直接i->s->k呢？所以f[i][j]中的j只需要取0,1。 于是就可以了
解法①的代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MAX=(
1<<
30);
const LL N=
2005;
LL n;
LL a[N][N];
LL f[N];
bool vis[N];
int main()
{
memset(vis,
false,
sizeof(vis));
memset(f,
127,
sizeof(f));
LL mn=MAX;
scanf(
"%I64d",&n);
for (LL u=
1;u<=n;u++)
for (LL i=u+
1;i<=n;i++)
{
scanf(
"%I64d",&a[u][i]);
a[i][u]=a[u][i];
mn=min(mn,a[u][i]);
}
for (LL u=
1;u<=n;u++)
for (LL i=
1;i<=n;i++)
if (u!=i)
{
a[u][i]-=mn;
f[u]=min(f[u],
2*a[u][i]);
}
for (LL u=
1;u<=n;u++)
{
LL t=
0;
for (LL i=
1;i<=n;i++)
if (f[t]>f[i]&&vis[i]==
false)
t=i;
vis[t]=
true;
for (LL i=
1;i<=n;i++) f[i]=min(f[i],f[t]+a[t][i]);
}
for (LL u=
1;u<=n;u++)
printf(
"%I64d\n",f[u]+(n-
1)*mn);
return 0;
}
解法②的代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const LL MAX=
1e15;
const LL N=
2005;
LL n;
LL a[N][N];
bool vis[N];
LL f[N][
2];
bool b[N][
2];
queue<pair<int,int> > q;
bool o[N];
void SPFA ()
{
memset(b,
false,
sizeof(b));
memset(f,
127,
sizeof(f));
for (LL u=
1;u<=n;u++)
{
if (o[u]==
false)
continue;
f[u][
0]=
0;b[u][
0]=
1;
q.push(make_pair(u,
0));
}
while (!q.empty())
{
LL i=q.front().first,j=q.front().second;
for (LL u=
1;u<=n;u++)
{
if (u==i)
continue;
LL t=min(f[i][j]+(j+
1)*a[i][u],MAX);
if (t<f[u][
0])
{
f[u][
0]=t;
if (b[u][
0]==
false)
{
b[u][
0]=
true;
q.push(make_pair(u,
0));
}
}
t=f[i][j];
if (j==
0&&t<f[u][
1])
{
f[u][
1]=t;
if (b[u][
1]==
false)
{
b[u][
1]=
true;
q.push(make_pair(u,
1));
}
}
}
q.pop();b[i][j]=
false;
}
}
int main()
{
memset(o,
false,
sizeof(o));
memset(vis,
false,
sizeof(vis));
memset(a,
127,
sizeof(a));
LL mn=MAX;
scanf(
"%I64d",&n);
for (LL u=
1;u<=n;u++)
for (LL i=u+
1;i<=n;i++)
{
scanf(
"%I64d",&a[u][i]);
a[i][u]=a[u][i];
mn=min(mn,a[u][i]);
}
for (LL u=
1;u<=n;u++)
for (LL i=
1;i<=n;i++)
if (u!=i)
{
a[u][i]-=mn;
if (a[u][i]==
0) o[u]=o[i]=
true;
}
SPFA();
for (LL u=
1;u<=n;u++)
printf(
"%I64d\n",f[u][
0]+(n-
1)*mn);
return 0;
}
