当前位置: 首页 > news >正文

插画师培训网站建设app登录wordpress

插画师培训网站建设,app登录wordpress,网站企业建设方案,网站建设的现状分析正题 题目链接:https://www.luogu.com.cn/problem/P7276?contestId39577 题目大意 nnn个点的一棵树#xff0c;kkk个关键点#xff0c;两个人从根出发分别走一段路径回到根。要求每个关键点至少被一个人经过#xff0c;求最短时间。 解题思路 相当于求两个覆盖所有关键点…正题 题目链接:https://www.luogu.com.cn/problem/P7276?contestId39577 题目大意 nnn个点的一棵树kkk个关键点两个人从根出发分别走一段路径回到根。要求每个关键点至少被一个人经过求最短时间。 解题思路 相当于求两个覆盖所有关键点的联通子图使得最大那棵最小。 树上只留下关键点和它们的祖先节点这样就变为了所有点都要经过也就是所有叶子都要经过。 然后比较显然的结论是一定会按照dfsdfsdfs从小到大的顺序走所以可以直接dpdpdp。设fi,j,kf_{i,j,k}fi,j,k​表示两个人分别走到i,ji,ji,j目前第二棵树的大小为kkk时第一棵树的最小大小。 注意转移x−ix-ix−i的时候权值得是dis(LCA(x,i),i)dis(\ LCA(x,i),i\ )dis( LCA(x,i),i )因为是联通子图上延伸下来一条路径。 时间复杂度O(n3)O(n^3)O(n3) 因为是比赛的时候写的代码改的所以比较丑。 code #includecstdio #includecstring #includealgorithm using namespace std; const int N420; struct node{int to,next; }a[N1]; int n,k,tot,num,ls[N],dep[N],f[N],lca[N][N],ans,dp[N][N][N],son[N]; bool mark[N]; void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return; } bool calc(int x,int fa){dep[x]dep[fa]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;f[y]x;mark[x]|calc(y,x);}return mark[x]; } void dfs(int x,int fa){if(!mark[x])return;bool flag1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||!mark[y])continue;flag0;break;}if(flag||x1)son[num]x;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);}return; } int LCA(int x,int y){while(dep[x]dep[y])xf[x];while(dep[y]dep[x])yf[y];while(x!y)xf[x],yf[y];return x; } int dis(int x,int y) {return dep[y]-dep[lca[x][y]];} int main() {scanf(%d%d,n,k);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}for(int i1;ik;i){int x;scanf(%d,x);mark[x]1;}calc(1,1);dfs(1,1);for(int i1;in;i)for(int j1;jn;j)lca[i][j]LCA(i,j);memset(dp,0x3f,sizeof(dp));ansdp[1][1][0];dp[1][1][0]0;son[num]1;for(int i2;inum;i)for(int x1;xi;x)for(int y1;yi;y){if(x!i-1y!i-1)continue;for(int z0;zn;z){int ddis(son[x],son[i]);dp[i][y][z]min(dp[i][y][z],dp[x][y][z]d);ddis(son[y],son[i]);if(zd)dp[x][i][z]min(dp[x][i][z],dp[x][y][z-d]);}}for(int i0;inum;i)for(int j0;jnum;j){if(i!numj!num)continue;for(int z0;zn;z)ansmin(ans,max(dp[i][j][z],z));}printf(%d\n,ans*2); }
http://wiki.neutronadmin.com/news/221272/

相关文章:

  • 网站后台管理系统php做企业推广
  • 永年网站建设开发公司资质哪里查
  • 广西建设厅查询网站哪里有零基础的电脑培训班
  • 科技 杭州 网站建设WordPress文章发布模块
  • 深圳东风大厦 网站建设东城做网站
  • 吉水县建设局网站手机怎样设计网站建设
  • 后台网站模板下载西服定制一般多少钱
  • 企业营销型网站建设开发深圳市移动端网站建设
  • 中国水电建设集团港航建设有限公司网站免费外贸电商平台
  • 如何建立微网站怎么看一个网站是不是织梦
  • 扁平化风格网站模板wordpress个人支付宝
  • 网站建设发展历程ppt如何利用视频网站做推广
  • 如何建立公司网站是什么wordpress标签logo
  • 自己建的网站如何做海外推广政务信息公开和网站建设自评
  • 排名网站却搜不到广州站是广州火车站吗
  • 企业网站推广设计凡科建站电话
  • 化妆品网站开发流程和进度安排小程序登录不了
  • 绵阳网站推广排名自己做的砍价网站
  • seo关键词是什么意思东莞优化电话
  • 广告网seo优化排名服务
  • 免费自助创建网站可以做砍价链接的网站
  • 网站开发用php还pyt h on中国软件是外包吗
  • 食品电子商务网站建设规划书网站建设维护报价
  • 抖音网站建设网站开发需要那些人才
  • 网站模板的组成体育器材网站建设方案
  • 婚恋网站排名前10图片 wordpress
  • 数据分析师培训重庆企业网站seo
  • 正能量视频免费网站免下载银行门户网站开发
  • 做企业的网站wordpress实现登录
  • 房租 做网站怎样重装电脑wordpress