Gravatar
┭┮﹏┭┮
积分:2922
提交:742 / 1645

Gravatar
ムラサメ
积分:1492
提交:375 / 742
数据太弱,建议加强
数据生成器:
int T=5,n=5000,m=(n-1)*2,k=n/10,len=10;
printf("%d\n",T);
while(T--){
printf("%d%d%d\n",n,m,k);
for(int i=1;i<=k;++i){
int id=(i-1)*len+1;
if(id!=1){
printf("%d%d%d\n",1,id,1);
printf("%d%d%d\n",id,1,1);
}
for(int j=id+1;j<id+len;++j){
printf("%d%d%d\n",j-1,j,1);
printf("%d%d%d\n",j,j-1,1);
}
}
for(int i=1;i<=k;++i){
printf("%d",i*len);
}
puts("");
}

Gravatar
op_组撒头屯
积分:2982
提交:327 / 662
回复 @Skylake
是初中有一次把咱叫去听高中的课的时候讲的,当时我听完大受震撼,以至于其他题都忘了就记着这一题hh

Gravatar
yrtiop
积分:2053
提交:304 / 803
回复 @组撒头屯 :
不记得了欸,可能我还没听吧,这题正解反而简单一点,次解更巧妙

Gravatar
op_组撒头屯
积分:2982
提交:327 / 662
回复 @Skylake :
我记得好早之前的集训讲过这题,没记错应该是不停按二进制分两组跑最短路,不过具体分法也忘了

Gravatar
yrtiop
积分:2053
提交:304 / 803
$\mathcal O(Tn\log n\log k)$ 的做法属实人类智慧,感觉比正解还巧妙