【CCF 201909-5】城市规划(LCA+暴力全排列40 & 树形dp100) Apare_xzc
城市规划(ccf 201909-5)
题面：
思路
1. 我一看求树上的距离，就想到了很喜欢的LCA, 可以O(1)求距离，然后又看m个节点选K个，一看，我能不能暴力dfs出C(m,k)的全排列呢？计算一下复杂度，发现前4个测试点可以过掉，于是先开心地写一发巨长的暴力（大的数据sort瞎搞的，没骗到分）
LCA + dfs暴力枚举点
//用户名 试题名称 提交时间 代码长度 编程语言 评测结果 得分 时间使用 空间使用
//<许智超> 城市规划 11-22 10:59 3.180KB C0X 错误 40 3.078s 15.37MB
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
const int maxm = 2e5+100;
int head[maxn],tot;
struct Node{
int to,Next,d;
}node[maxm];
void initEdge()
{
tot = 0;
memset(head,-1,sizeof(head));
}
void addedge(int from,int to,int d)
{
node[tot].to = to;
node[tot].d = d;
node[tot].Next = head[from];
head[from] = tot++;
}
int good[100500];
int First[maxn],cnt;
int dfn[maxn*2];
int deep[maxn*2];
int father[maxn];
int disToRoot[maxn];
int idd[maxn]; ///是干啥用的？
bool vis[maxn];
bool cmp(int x,int y)
{
return disToRoot[x]<disToRoot[y];
}
void dfs(int x,int dep)
{
vis[x] = true;
dfn[++cnt] = x;
deep[cnt] = dep;
First[x] = cnt;
for(int i=head[x];i!=-1;i=node[i].Next)
{
int to = node[i].to;
int d = node[i].d;
if(vis[to]) continue;
father[to] = x;
disToRoot[to] = disToRoot[x]+d;
dfs(to,dep+1);
dfn[++cnt] = x;
deep[cnt] = dep;
}
}
int ST[maxn][20];
int Log2[maxn]={-1};
void preRMQ(int m)
{
int n = m*2-1;
for(int j=1;j<=n;++j) ST[j][0] = j;
for(int i=1;(1<<i)<=n;++i)
{
for(int j=1;j+(1<<i)-1<=n;++j)
{
int a = ST[j][i-1], b = ST[j+(1<<(i-1))][i-1];
ST[j][i] = deep[a]>deep[b]?b:a;
}
}
}
int LCA(int xx,int yy)
{
int x = First[xx], y = First[yy];
if(x>y) swap(x,y);
int i = Log2[y-x+1];
int a = ST[x][i], b = ST[y-(1<<i)+1][i];
int p = deep[a]>deep[b]?b:a;
return dfn[p];
}
long long calDis(int px,int py)
{
int fa = LCA(px,py);
return disToRoot[px]-disToRoot[fa]-disToRoot[fa]+disToRoot[py];
}
int r[105000];
bool hasCelected[201900];
long long ans;
void solve(int k,int flag=0) //计算K个点两两之间的最短距离
{
long long sum = 0;
for(int i=1;i<=k;++i)
{
for(int j=i+1;j<=k;++j)
sum += flag?calDis(r[i],r[j]):calDis(good[r[i]],good[r[j]]);
}
if(ans>sum) ans = sum;
}
void f1(int x,int M,int k) //C(M,k)
{
if(x==k+1)
{
solve(k);
return;
}
for(int i=r[x-1]+1;i<=M;++i)
{
if(hasCelected[i]) continue;
hasCelected[i] = true;
r[x] = i;
f1(x+1,M,k);
hasCelected[i] = false;
}
}
int main()
{
int n,m,k,NN,x,y,d;
scanf("%d%d%d",&n,&m,&k);
NN = n*2+10;
for(int i=1;i<NN;++i)
Log2[i] = Log2[i>>1]+1;
for(int i=1;i<=m;++i)
scanf("%d",good+i);
initEdge();
for(int i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&d);
addedge(x,y,d);
addedge(y,x,d);
}
cnt = 0;
int root = good[1];
father[root] = root;
disToRoot[root] = 0; //root = 1
dfs(root,1);
preRMQ(n);
if((m<=2000&&k<=2)||(m<=16&&k<=16))
{
ans = 1e16;
r[0] = 0;
f1(1,m,k);
printf("%lld\n",ans);
}
else
{
ans = 1e16;
int upM = m;
if(m>2000) upM = 2000;
for(int kk=1;kk<=upM;++kk)
{
cnt = 0;
for(int i=0;i<=n;++i) vis[i] = false;
int root = kk;
father[root] = root;
disToRoot[root] = 0; //root = 1
dfs(root,1);
preRMQ(n);
for(int i=1;i<=m;++i) idd[i] = good[i];
sort(idd+1,idd+1+m,cmp);
for(int i=1;i<=k;++i) r[i] = idd[i];
solve(k,1);
}
printf("%lld\n",ans);
}
return 0;
}
思路：
2. 想不到什么好办法，于是去网上看题解，只有一个大牛写了题解，链接：https://blog.csdn.net/code92007/article/details/102022390
是树形DP，我觉得非常妙。而且这种2e3左右的很多都是N^2的DP
我们换个思路，不直接枚举点，而是计算每条边对于答案的贡献
———————————————————————————————————
dp[u][p] 表示的是以u为根节点的这棵树中,选取了p个点的距离之和的最小值
要满足恰好选了K个点，那么如果以u为根节点的数中选了p个点，那么整个树
除了u这棵子树的所有树all-u就要选q个子节点
对于u的儿子节点v u,v,w
令 tmp[p] = dp[u][p]
先往下搜索子节点v，得到dp[v][...]的信息
父节点u和子节点v之间的边长为w
然后我们来更新dp[u][...]
最终的答案是dp[root][K]
对于u->v:w 这条边来说
在还没有用v来更新u之前，子树v对于树u的贡献为0，
就是说现在的以u为根的树tree(u)相当于tree(u)去掉了以v为根节点的子树，即为tree(u-v)
如果要从子树tree(v)中选p个重要节点，那么tree(root-v)中就要选K-p个
那么状态是怎么转移的呢？
如果在tree(v)中选了x个点，在tree(root-v)中选了y个点，那么计算总距离的时候u->v:w这条
边对答案的贡献是 w * (x*y)
/* 用户名 试题名称 提交时间 代码长度 编程语言 评测结果 得分 时间使用 空间使用 <许智超> 城市规划 11-23 10:41 2.626KB C0X 正确 100 140ms 21.63MB */
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+100;
int head[maxn],tot;
struct Node{
int to,Next,d;
}node[maxn*2];
void initEdge()
{
tot = 0;
memset(head,-1,sizeof(head));
}
void addedge(int from,int to,int d)
{
node[tot].to = to;
node[tot].d = d;
node[tot].Next = head[from];
head[from] = tot++;
}
int dp[maxn][102],k;
int tree_u_v[102];
bool good[maxn];
int num[maxn]; //num[u]表示以u为根节点的树中重要节点的个数
//get到一种新的写法，对于树的遍历不用vis,只要遍历子节点的时候，if(v==fa) continue就好了
/* dp[u][t] 的意义为： 以u为根节点的树中选择了t个重要节点(其它的所有节点中一共选了k-t个节点) 这棵树中的所有重要节点两两之间路径之和的最小值 */
void dfs(int u,int fa) //对树进行先序遍历，在回溯的时候用子节点的信息去更新父节点的信息
{
dp[u][0] = 0; //初始化,因为一个树一个重要节点都没选，点之间的路径之和当然为0
//num[u] = 0;
if(good[u]) //如果节点u是一个重要节点
{
dp[u][1] = 0; //那么从这棵树中选一个重要节点就选它自己，没有其他节点和它连接，最小值当然是0
num[u] = 1; //记录以u为根节点的子树当前已知有一个重要节点
}
for(int i=head[u];i!=-1;i=node[i].Next) //常规写法，遍历节点u所有可达的节点v(遍历所有的儿子节点v)
{
if(node[i].to==fa) continue;
int v = node[i].to; //v代表节点u的儿子节点
int d = node[i].d; //d代表u->v这条边的长度
dfs(v,u); //先往下搜索子节点v
//搜索完之后进行回溯，用dp[v][...]的信息更新dp[u][...]的信息
for(int j=0;j<=k;++j)
tree_u_v[j] = dp[u][j]; //先用tree_u_v[]这个数组当做一个临时变量区，存储被dp[v]更新之前的dp[u]
int nU = min(k,num[u]); //因为最多选K个重要节点，所以可以取一个num[u]和K的最小值，避免多余的计算
int nV = min(k,num[v]);//同上
num[u] += num[v]; //以v为节点的树有num[v]个重要节点，然后用num[v]更新父节点u代表的树的重要节点数
for(int j=0;j<=nU;++j)
{
for(int t=0;t<=nV&&t+j<=k;++t)
{
dp[u][j+t] = min(1ll*dp[u][j+t],1ll*(k-t)*t*d+tree_u_v[j]+dp[v][t]);
}
}
/* 因为我们的目的是求选择的K个点之间两两的距离之和。我们要统计书上每一条边对于答案的贡献。 边的长度为d。我们用dfs先序遍历搜索，回溯的时候用子树v的信息来更新u的信息。tree_u_v[] 这个数组相当于是一个缓冲区，记录了用v更新之前u的信息。 dp[u][j+t] = min(1ll*dp[u][j+t],1ll*(k-t)*t*d+tree_u_v[j]+dp[v][t]); 这句代码其 实是在用u--->v这条边对于答案的贡献来更新dp[u][]的信息。 dp[v][t]代表的是以顶点v为根节点的子树含有v个重要节点的最小值 tree_u_v[] 中存储的是整个树减去v这棵树的信息。 如果用dp[v][t]来更新dp[u][], 那么以v为 根节点的子树中有t个重要节点，这些节点都在u->v这条边 的下方，而一共选k个节点，u->v这条边 的上方就有k-t个重要节点。 从这两个点集中各取一个点，两两之间的路径必定都含u->v这条边。 一共有 t * (k-t) 中组合。 所以 t * (k-t) * d, 就是用v更新u之后，边u->v:d 对答案增加的贡献。 我们用 (k-t)*t*d + tree_u_v[j] + dp[v][t] 来更新 dp[u][j+t] */
}
}
int main()
{
int n,m,x,y,d;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;++i)
scanf("%d",&x), good[x] = true;
initEdge();
for(int i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&d);
addedge(x,y,d);
addedge(y,x,d);
}
memset(dp,0x3f,sizeof(dp));
dfs(1,-1);
printf("%d\n",dp[1][k]);
return 0;
}
我爱树，我爱DP，我也爱LCA~
投递知乎等公司10个岗位 >