动态淀粉质即可
#include "rts.h" #include #include #include #include #include const int maxn = 300300; int per[maxn],vis[maxn]; typedef long long ll; std::map<int,int> ans[maxn]; int N; inline int get(int x,int y){return explore(x,y); } namespace list{const int LEFT=1,RIGHT=0;inline void solve(int to,int&l,int&r,int type=LEFT){if(l==to||r==to)return ;if(type == LEFT){int p=get(l,to);if(vis[p])solve(to,l,r,RIGHT);else vis[p]=1,solve(to,l=p,r,type);}else{int p=get(r,to);vis[p]=1,solve(to,l,r=p,type);}} } namespace wwj{int n;const double alpha=0.6;struct sol_tree{int size,rt;std::map<int,sol_tree*> son;inline sol_tree(int p){size=1,rt=p;}inline ~ sol_tree(){son.clear();}};struct T{int to,nxt;}way[maxn<<1];int h[maxn],num;inline void adde(int x,int y){way[++num]={y,h[x]},h[x]=num;way[++num]={x,h[y]},h[y]=num;}inline void up(int&x,int y){if(xy;}sol_tree ** rebd;int vis[maxn];namespace dfz{int vis[maxn],size[maxn];inline void init(){for(int i=1;i<=n;++i)vis[i]=1;}inline void getsz(int x){vis[x]=size[x]=1;for(int i=h[x];i;i=way[i].nxt)if(!vis[way[i].to])getsz(way[i].to),size[x]+=size[way[i].to];vis[x]=0;}int rt,v;inline void getrt(int x,int al){vis[x]=1;int ms=0;for(int i=h[x];i;i=way[i].nxt)if(!vis[way[i].to])getrt(way[i].to,al),up(ms,size[way[i].to]);if(std::max(al-size[x],ms)x;vis[x]=0;}inline int getroot(int x){getsz(x),v=1e9,getrt(x,size[x]);return rt;}inline sol_tree* sol(int x){x=getroot(x),vis[x]=1;sol_tree * ret = new sol_tree(x);for(int i=h[x];i;i=way[i].nxt)if(!vis[way[i].to]){sol_tree * tmp=ret->son[way[i].to]=sol(way[i].to);ret->size+=tmp->size;}return ret;}inline void dfscls(sol_tree * rt){vis[rt->rt] = 0;for(std::pair<int,sol_tree*>i:rt->son)dfscls(i.second);delete rt;}}int cnt,sumsz;inline void rebuild(sol_tree ** rebd){++cnt;sol_tree* & rt = * rebd;int R = rt -> rt;sumsz+=rt->size;dfz::dfscls(rt);rt=dfz::sol(R);}inline int ins(sol_tree*&rt,int to){int p = get(rt -> rt,to);if(!vis[p]){sol_tree*&tmp=rt -> son[p] = new sol_tree(p);adde(rt -> rt,p),vis[p]=1;int res=0;if(p!=to)rt->size+=res=ins(tmp,to);if(rt -> size * alpha + 1 < tmp -> size)rebd =&rt;return res+1;}else{sol_tree*&tmp=rt->son[p];int res=0;rt->size+=res=ins(tmp,to);if(rt -> size * alpha + 1 < tmp -> size)rebd =&rt;return res;}}inline void solve(){srand(time(0));for(int i=1;i<=n;++i)per[i]=i;for(int i=1;i<=2;++i)std::random_shuffle(per+1,per+n+1);dfz::init();vis[1]=1;sol_tree * rt = new sol_tree(1);int cnt=n-1;while(cnt){int i=rand()%n+1;if(!vis[per[i]]){rebd=0;cnt-=ins(rt,per[i]);if(rebd)rebuild(rebd);}}} } void play(int n, int T, int dataType){N=wwj::n=n;if(dataType == 3){srand(time(0));for(int i=1;i<=n;++i)per[i]=i;for(int i=1;i<=10;++i)std::random_shuffle(per+1,per+n+1);vis[1]=1;for(int i=1,l=1,r=1;i<=n;++i)if(!vis[per[i]])list::solve(per[i],l,r);}else{wwj::solve();} }
转载于:https://www.cnblogs.com/skip1978/p/10342923.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
Duilib中list控件支持ctrl和shif多行选中的实现
[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif
win10系统 微软输入法 于eclipse ctrl+shif+f冲突间接处理办法
Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif
读LDD3，内存映射与DMA--PAGE_SHIF…
VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】
更换iBus五笔的左与右Shif
sublime ctrl+shif+f 没用解决办法
idea 对 ctrl + z 的撤销 是 ctrl + shif + z
计算机最早的设计师应用于,计算机应用基础选择题doc.doc
win10自带截图神器：Win+Shift+S
Python基础之文件目录操作
python简述目录_Python基础之文件目录操作(示例代码)
tp5 如何做数据采集
任务2-7(服务器字体+阿里巴巴矢量库)
html标签（1)：h1~h6,p,br,pre,hr
TI 电量计介绍与芯片选型指南
几款TI电源芯片简介
TI DSP芯片C2000系列读取FLASH数据
德州仪器(Ti)平台嵌入式开发基础
TI三相电机智能栅极驱动芯片特点分类
省选模拟（12.08） T3 圈圈圈圈圈圈圈圈
Hadoop生态圈技术栈（上）
大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询
小猿圈之Linux下Mysql 操作命令
大数据Hadoop生态圈常用面试题
大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作
备战Noip2018模拟赛11（B组）T3 Monogatari 物语
【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码
NYOJ 78 圈水池
递归问题 跑道 汽车 绕圈问题 Python实现
Hadoop生态圈（三）：MapReduce
微信公众账号
微信扫一扫加关注
