题目大意
给定一棵大小为$n(n \le 3000)$的树，带边权
请你给出一个长度为$k(k \le n)$的序列$\{a_i\}$
要求序列中两两元素不同，请你最小化$\sum\limits_{i=1}^{k-1}{dis(a_i,a_{i+1})}$
解题报告
我们看一看这个式子可以发现实际上是要我们给出一个大小为$k$的连通块
问你这个连通块内的边权乘上$2$再减掉直径的最小值是多少
于是我们定义$h_{i,j}$为$i$的子树中选$j$个点，还没有考虑直径的最小花费
$f_{i,j}$表示在$i$的子树里，选$j$个点，直径包含$i$的最小花费
$g_{i,j}$表示在$i$的子树里，选$j$个点，已经考虑过直径且直径不包含$i$的最小花费
然后我们暴力$DP$就可以了
我们的时间复杂度是$T(n)=\sum\limits_{i}{\sum\limits_{fa_i=fa_j}{size_i \cdot size_j}}$
仔细想一想的话，每一堆点只会在$LCA$处被计算，时间复杂度是$O(n^2)$的
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3009;
const int M = N << 1;
const LL INF = 1e18;
int n,k,head[N],nxt[M],to[M],cost[M],sz[N];
LL vout=INF,f[N][N],g[N][N],h[N][N];
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void AddEdge(int u, int v, int c) {
static int E = 1; cost[E+1] = cost[E+2] = c;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
void update(int w, int fa) {
fill(f[w], f[w]+1+N, INF);
fill(g[w], g[w]+1+N, INF);
fill(h[w], h[w]+1+N, INF);
f[w][1] = g[w][1] = h[w][1] = 0; sz[w] = 1;
for (int i=head[w],t;i;i=nxt[i]) {
if ((t=to[i]) != fa) {
update(to[i], w);
for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
for (int j=1;j<=sz[t];j++) {
g[w][x+j] = min(g[w][x+j], g[w][x] + h[t][j] + tmp);
g[w][x+j] = min(g[w][x+j], f[w][x] + f[t][j] + cost[i]);
g[w][x+j] = min(g[w][x+j], h[w][x] + g[t][j] + tmp);
}
}
for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
for (int j=1;j<=sz[t];j++) {
f[w][x+j] = min(f[w][x+j], h[w][x] + f[t][j] + cost[i]);
f[w][x+j] = min(f[w][x+j], f[w][x] + h[t][j] + tmp);
}
}
for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
for (int j=1;j<=sz[t];j++)
h[w][x+j] = min(h[w][x+j], h[w][x] + h[t][j] + tmp);
}
sz[w] += sz[t];
}
}
vout = min(vout, f[w][k]);
vout = min(vout, g[w][k]);
}
int main() {
n = read(); k = read();
for (int i=2,u,v;i<=n;i++) {
u = read(); v = read();
AddEdge(u, v, read());
}
update(1, 1);
printf("%lld\n",vout);
return 0;
}
I’m not sure exactly why but this weblog is loading extremely slow for
me. Is anyone else having this issue or is it a problem on my end?
I’ll check back later on and see if the problem still exists.
Admiring the persistence you put into your website and in depth information you offer.
It’s nice to come across a blog every once in a while that isn’t the same old rehashed material.
Excellent read! I’ve bookmarked your site and I’m adding your RSS feeds to my Google account.
In fact when someone doesn’t be aware of after that its up to other viewers that they will help, so here it occurs.
It’s an remarkable post in favor of all the web viewers; they will obtain benefit from it I am sure.
Thanks for another excellent post. Where else may anyone get that kind of information in such an ideal manner of
writing? I’ve a presentation next week, and I’m at the
search for such information.
What’s up to all, the contents present at this site are in fact amazing
for people experience, well, keep up the nice work fellows.
I love what you guys are up too. This sort of clever work and exposure!
Keep up the fantastic works guys I’ve included you guys to
my blogroll.
I needed to thank you for this very good read!!
I definitely loved every bit of it. I have you saved
as a favorite to check out new stuff you post…
I used to be able to find good info from your articles.
Good day! I simply want to offer you a huge thumbs up for your great info you have right
here on this post. I will be coming back to your web
site for more soon.
Thank you for another fantastic article. Where else
may just anyone get that kind of information in such an ideal way of writing?
I have a presentation next week, and I’m on the look for such information.
Hi there to every body, it’s my first pay a visit of this blog; this weblog carries amazing
and actually fine data designed for visitors.
obviously like your website however you have to take a look at
the spelling on quite a few of your posts. Many of them
are rife with spelling issues and I in finding it very bothersome to tell the
truth nevertheless I’ll certainly come back again.
Hey! Do you use Twitter? I’d like to follow you if that would be ok. I’m absolutely enjoying your blog and look forward to new posts.
Hi i am kavin, its my first time to commenting anywhere, when i read this paragraph i thought i could also create
comment due to this good piece of writing.
Thank you a lot for sharing this with all of us you actually realize what you’re talking
about! Bookmarked. Kindly also discuss with my site =).
We will have a hyperlink change agreement between us
A motivating discussion is worth comment. I think that you need to publish more on this issue, it may not be a taboo matter but
generally people don’t speak about such subjects. To the next!
Best wishes!!
Your way of telling all in this article is in fact nice,
every one be able to without difficulty understand it, Thanks a lot.
I am not sure where you’re getting your info, but good topic.
I needs to spend some time learning much more
or understanding more. Thanks for wonderful information I was looking for this
info for my mission.
Greetings from California! I’m bored to death at work so I decided to check out
your blog on my iphone during lunch break.
I really like the info you provide here and can’t
wait to take a look when I get home. I’m shocked at how quick your blog loaded on my cell phone ..
I’m not even using WIFI, just 3G .. Anyhow, very good
blog!
Spot on with this write-up, I honestly think this web site
needs a lot more attention. I’ll probably be back again to see more, thanks for the info!
Thanks for any other informative site. The place else could I get that kind of information written in such
an ideal means? I have a undertaking that I am just now working
on, and I have been at the look out for such information.
You ought to take part in a contest for one of the greatest websites on the web.
I am going to highly recommend this blog!
You are a very smart individual!