[考试反思]0416省选模拟72:停滞
大约是来搞笑的了。
$T1$想到了$wqs$二分但是不会(或者说根本没往这个方向想)$dp$。
$T2$神仙题暂且不管($15$是全场最高但是有个啥用?)
$T3$的话会$30pts$的状压,但是觉得对我整场的分数并没有什么作用于是也就没有写。随便输出了个$0$拿走$10pts$
主观来讲,我大概是没长脑子,啥都想不出来
客观来讲,题有一点不对胃口,好像考试的时候始终不太敢去猜测性质然后就开始写代码
那些用的不多的知识点以及扩展出来的性质就更不敢用了,可能也是导致这样的原因
大约多做题是一个合理的解决办法,至少下次再遇到这些东西,我不会慌了。。。
又把锅甩给了下次啊。。。
T1:新访问计划
大意:边权树,要求遍历每条树边至少一次最后回到根,可以花费$c$的代价直接传送到任意点最多$k$次。求最小代价。多测。$sum n,k le 10^5,n le 2 imes 10^4,w_i,c le c imes 10^4$
可以转化题意:首先要求回路那么所有树边必须走一次,接下来你可以用树边 和 代价为$c$的树上路径至多$k$条 来覆盖整棵树。求最小代价。
可以搞出一个$dp$表示$f[i][j][0/1]$表示是否有一个未配对(可以再次转弯的)路径连向当前$i$且子树内完全被覆盖而已经申请了$j$条路径的最小代价。
子树归并。$0/1 + 0/1 ightarrow 0/1$共$8$种情况其中有一种不合法剩下的按照含义转移即可。
复杂度是$O(n^2)$的。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 2222 4 #define inf 1000000000 5 int f[S][S],g[S][S],n,fir[S],l[S<<1],to[S<<1],w[S<<1],ec,k,c,sz[S],F[S],G[S],tot; 6 void link(int a,int b,int x){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;w[ec]=x;} 7 void con(int a,int b,int x){link(a,b,x);link(b,a,x);} 8 void dfs(int p,int fa){ 9 sz[p]=1; f[p][1]=g[p][0]=0; f[p][0]=g[p][1]=inf; 10 for(int _=fir[p],z;_;_=l[_])if((z=to[_])!=fa){ 11 dfs(z,p); int W=w[_]; 12 for(int i=0;i<=sz[p]+sz[z];++i)F[i]=G[i]=inf; 13 for(int i=0;i<=sz[p];++i)for(int j=0;j<=sz[z];++j) 14 G[max(0,i+j-1)]=min(G[max(0,i+j-1)],f[p][i]+f[z][j]), 15 F[i+j]=min(F[i+j],f[p][i]+f[z][j]), 16 F[i+j]=min(F[i+j],f[p][i]+g[z][j]+W), 17 G[i+j]=min(G[i+j],f[p][i]+g[z][j]), 18 F[i+j]=min(F[i+j],g[p][i]+f[z][j]), 19 F[i+j+1]=min(F[i+j+1],g[p][i]+g[z][j]), 20 G[i+j]=min(G[i+j],g[p][i]+g[z][j]+W); 21 sz[p]+=sz[z]; 22 for(int i=0;i<=sz[p];++i)f[p][i]=F[i],g[p][i]=min(G[i],F[i]); 23 } 24 } 25 int main(){//freopen("ex_newmzz3.in","r",stdin); 26 while(cin>>n>>k>>c){ 27 for(int i=1,a,b,x;i<n;++i)scanf("%d%d%d",&a,&b,&x),con(a,b,x),tot+=x; 28 dfs(0,0); 29 int ans=inf; 30 for(int i=0;i<=k;++i)ans=min(ans,min(g[0][i],f[0][i])+c*i); 31 cout<<ans+tot<<endl; 32 for(int i=0;i<n;++i)fir[i]=0; ec=tot=0; 33 }}
这题的含义让人不难想到$wqs$二分。
但是我们的要求是,第二维也就是已使用的路径数不能超过$k$。所以我们再开一个数组存储在此代价下最小的路径使用数。
二分并据此查找合适的$c$
如果对于某个特定的$c_0$最有决策下使用的路径书是$x$,对于$c_1$也是,那么在这两个代价下的决策也一定是完全一样的。
所以说,我们可以先进行一次$dp$,然后看最有决策使用的路径数是否超过$k$
如果没有超过那么就是说最优解就合法可以直接输出。否则,我们一定希望我们恰好选择$k$条路径。
那么通过$wqs$去找恰好$k$条路径的方案,如果不存在恰好为$k$的,那么也当成$k$去计算就好了。
(此时一定是存在多条路径,选择它们的收益相同,所以才会一选都选一不选都不选,然而恰好选$k$个是最优的,依次贡献答案是最佳的)
总的时间复杂度是$O(n log w)$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 100005 4 #define ll long long 5 ll f[S][2],tot;int g[S][2],n,fir[S],l[S<<1],to[S<<1],w[S<<1],ec,k,c; 6 void link(int a,int b,int x){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;w[ec]=x;} 7 void con(int a,int b,int x){link(a,b,x);link(b,a,x);} 8 void upd(ll&F,int&G,int p,int z,int x,int y,int df,int dg){ 9 ll nf=df+f[p][x]+f[z][y],ng=dg+g[p][x]+g[z][y]; 10 if(nf<F||(nf==F&&ng<G))F=nf,G=ng; 11 } 12 void dfs(int p,int fa){ 13 f[p][1]=c; g[p][1]=1; f[p][0]=0; g[p][0]=0; 14 for(int _=fir[p],z;_;_=l[_])if((z=to[_])!=fa){ 15 dfs(z,p); int W=w[_],g1,g0;ll f0=1e17,f1=1e17; 16 upd(f0,g0,p,z,1,1,-c,-1); 17 upd(f1,g1,p,z,1,1, 0, 0); 18 upd(f1,g1,p,z,1,0, W, 0); 19 upd(f0,g0,p,z,1,0, 0, 0); 20 upd(f1,g1,p,z,0,1, 0, 0); 21 upd(f1,g1,p,z,0,0, c, 1); 22 upd(f0,g0,p,z,0,0, W, 0); 23 f[p][1]=f1; f[p][0]=f0; g[p][1]=g1; g[p][0]=g0; 24 } 25 } 26 int main(){//freopen("ex_newmzz3.in","r",stdin); 27 while(cin>>n>>k>>c){ 28 for(int i=1,a,b,x;i<n;++i)scanf("%d%d%d",&a,&b,&x),con(a,b,x),tot+=x; 29 dfs(0,0); 30 int C=c,l=0,r=1000000000,b;ll ans=g[0][0]>k?1e18:f[0][0]; 31 while(c=l+r>>1,l<=r){ 32 dfs(0,0); 33 if(g[0][0]<=k)r=c-1,b=c;else l=c+1; 34 } 35 c=b;dfs(0,0); 36 ans=min(ans,f[0][0]+k*(C-c)); 37 cout<<ans+tot<<endl; 38 for(int i=0;i<n;++i)fir[i]=0; ec=tot=0; 39 }}