记总边权为\(len\)。 如果不可以乘车，那么答案就是\(len*2\)，因为最优解时每条边都被经过两次。 如果可以乘车，那么每次乘车等价于将两个点之间的路径的经过次数-1，并给总花费加上\(C\)。 又由于必须走着经过每一条边至少一次，所以乘车的路径不可以相交。 答案必须至少有\(len\)。 随后问题等价于用不超过\(K\)条路径覆盖原树，每条路径花费为\(C\)，未覆盖的边的花费为原边权的最小总花费，加上\(len\)就是答案。 先考虑前55分的做法。 设\(f[i][j]\)表示在\(i\)子树内乘坐了\(j\)次巴士，且有一条巴士路径的一端是\(i\)的最小花费。 设\(g[i][j]\)表示在\(i\)子树内乘坐了\(j\)次巴士，不要求\(i\)是某条巴士路径的一段的最小花费。 这样可以用\(O(n^2)\)的树型DP解决，在这里不详细阐述。 如何改进？ DP的第一维状态难以省去，而表示坐车次数的第二维状态或许可以用其他方式代替。 设函数\(F(cost)=(x,y)\)表示不限坐车次数，单次坐车花费改成\(cost\)时，最小总花费为\(x\)，坐车次数为\(y\)。 其中，如果存在一条路径使得路径边权和等于\(cost\)，那么选择走路而不坐车。 可以发现\(cost\)增大时，\(y\)单调不增，且\(y\)不是连续的。但是\(cost\)和\(x\)没有单调关系。 根据前一个性质，如果对\(F\)的\(y\)进行一次差分，\(F(cost-1)_y-F(cost)_y\)会等于\(F(cost)\)方案中未被覆盖的路径长等于\(cost\)的路径数，它们处于一个均衡点上，\(cost\)变大必定走路，\(cost\)变小必定尽量坐车。 有一种方式理解\(x\)和\(y\)的关系，即\(x=y*cost+sumw\)，其中\(sumw\)是未被覆盖的边的边权之和。 \(F\)的求值是通过\(O(n)\)的DP实现的，做法下面再讲。 首先判断\(F(C)\)的\(y\)是否满足\(y\leq K\)，显然这样直接找到了最优解，输出\(x\)。 否则此时\(y > K\)。可以证明坐满\(K\)次车一定是最优的：因为要从\(y-K\)条路径中选一些改成走路，已经割舍一部分利益了，那么剩下的\(K\)条路径一定要选择坐车，不然答案将更劣。 我们二分\(cost\)的取值，直到\(y\)为最大的，小于等于\(K\)的值为止。 此时\(cost\)是大于\(C\)的（因为\(K\)要减小，\(cost\)必须要增大）。 此时\(F(cost)\)对应着一种坐车方案，坐了\(y\)次车。 题解给出了一个奇怪定理，可是我不会证明，只能感性理解： 如果我有一种在费用为\(c\)时乘坐\(k\)次巴士的最佳方案，不论坐车费用改为多少，如果一定要坐\(k\)次巴士，按这种方案坐\(k\)次车一定是最优的。 将这种方案的坐车费用直接修改成\(C\)，其总费变为\(y*C+sumw\). 那么此时答案为\(len+F(cost)_x+(C-cost)*y\). 注意这依然是不对的，如果二分出来的\(F(cost)\)的\(y\)小于\(K\)，那么说明若\(cost\)再减小1，\(y\)将直接跳过\(K\)变成大于\(K\)。根据\(F\)的性质，\(F(cost)\)的方案存在\(F(cost-1)_y-F(cost)_y\)条不坐车的路径的边权之和为\(cost\)。此时我们多出了\(K-y\)次坐车机会可以使用而且\(C<cost\)，那当然是尽可能把这些长度为\(cost\)的路径换成一次只需\(C\)的巴士！ 那么修正后的答案是\(len+F(cost)_x+(C-cost)*y+(C-cost)*(K-y)\)。 化简得到\(len+F(cost)_x+(C-cost)*K\)。 简单讲讲\(F(cost)\)的求法： 记\(f[i]\)表示\(i\)子树内有一条巴士路径的一端是\(i\)的最小花费及其乘坐巴士次数； \(g[i]\)表示\(i\)子树内不要求有一条巴士路径一端为\(i\)的最小花费及其乘坐巴士次数。 设当前遍历到\(i\)，则有初始状态\(f[i]=(cost,1)\)和\(g[i]=(0,0)\) 接着枚举\(i\)的儿子\(j\)，有如下转移： \[ \begin{aligned} f[i]&=min\{(f[i]_x+g[j]_x+w_j,f[i]_y+g[j]_y)\;,\;(g[i]_x+f[j]_x,g[i]_y+f[j]_y)\}\\ g[i]&=min\{(f[i]_x+f[j]_x-cost,f[i]_y+f[j]_y-1)\;,\;(g[i]_x+g[j]_x+w_j,g[i]_y+g[j]_y)\} \end{aligned} \] 计算完成后还有\(f[i]=min\{f[i]\;,\;(g[i]_x+cost,g[i]_y+1)\}\)，最后还有\(g[i]=min\{g[i]\;,\;f[i]\}\) 最终\(F(cost)=g[root]\)。
#include <cstdio> using namespace std; const int N=100005,inf=2000000000; int n,K,C,sumw; int h[N],tot; struct Edge{int v,w,next;}G[N*2]; int cost; struct Data{ int x,y; Data(){} Data(int _x,int _y){x=_x;y=_y;} friend bool operator < (const Data &u,const Data &v){ if(u.x!=v.x) return u.x<v.x; return u.y<v.y; } }; Data f[N],g[N]; inline Data min(Data x,Data y){return x<y?x:y;} inline void addEdge(int u,int v,int w){ G[++tot].v=v; G[tot].w=w; G[tot].next=h[u]; h[u]=tot; } void init(){ sumw=0; tot=0; for(int i=0;i<=n;i++) h[i]=0; } void dfs(int u,int fa){ f[u]=Data(cost,1); g[u]=Data(0,0); for(int i=h[u],v;i;i=G[i].next) if((v=G[i].v)!=fa){ dfs(v,u); Data tf=min(Data(f[u].x+g[v].x+G[i].w,f[u].y+g[v].y), Data(g[u].x+f[v].x,g[u].y+f[v].y)); Data tg=min(Data(f[u].x+f[v].x-cost,f[u].y+f[v].y-1), Data(g[u].x+g[v].x+G[i].w,g[u].y+g[v].y)); f[u]=min(tf,Data(tg.x+cost,tg.y+1)); g[u]=min(tf,tg); } } int solve(int cst){ cost=cst; dfs(0,-1); return g[0].y; } int main(){ while(~scanf("%d%d%d",&n,&K,&C)){ init(); for(int i=1;i<n;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addEdge(u,v,w); addEdge(v,u,w); sumw+=w; } if(solve(C)<=K){ printf("%d\n",sumw+g[0].x); continue; } int l=C+1,r=inf,mid,ans; while(l<=r){ int mid=(l+r)>>1; if(solve(mid)>K) l=mid+1; else ans=mid,r=mid-1; } solve(ans); //printf("%d\n",sumw+g[0].x-(ans-C)*K); printf("%d\n",sumw+g[0].x-(ans-C)*(K-g[0].y)-(ans-C)*g[0].y); } return 0; }转载于:https://www.cnblogs.com/RogerDTZ/p/8626641.html
