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

河北省建设招标网站做网站兰州

河北省建设招标网站,做网站兰州,交易网站域名,口碑好的网站建设价格正题 题目链接:https://www.luogu.com.cn/problem/P3573 题目大意 nnn个点mmm条边的DAGDAGDAG#xff0c;删掉一个点使得最长路最短。 解题思路 先跑一遍拓扑排序 dsids_idsi​表示以iii结尾的最长路#xff0c;dtidt_idti​表示以iii开头的最长路#xff0c;用拓扑序dp可…正题 题目链接:https://www.luogu.com.cn/problem/P3573 题目大意 nnn个点mmm条边的DAGDAGDAG删掉一个点使得最长路最短。 解题思路 先跑一遍拓扑排序 dsids_idsi​表示以iii结尾的最长路dtidt_idti​表示以iii开头的最长路用拓扑序dp可以搞定 定义两个点集SSS和TTT我们先将所有所有点放入TTT集合并且把dtdtdt放入一个数据结构里。 然后按照拓扑序枚举从小到大删除哪个点枚举到的点xxx我们把dtxdt_xdtx​从数据结构里删除对于y−xy-xy−x我们可以把dsydtx1ds_ydt_x1dsy​dtx​1从数据结构里删除。 然后查询最小值统计答案 之后把dsxds_xdsx​和对于x−yx-yx−y我们有dsxdty1ds_xdt_y1dsx​dty​1都丢进数据结构里。 这里用树状数组二分统计答案。 时间复杂度O(nlog⁡2n)O(n\log^2 n)O(nlog2n) codecodecode #includecstdio #includecstring #includealgorithm #includevector #includequeue #define lowbit(x) (x-x) using namespace std; const int N1e610; struct node{int to,next; }a[N]; queueint q; int n,m,cnt,ans,id; int in[N],top[N],ds[N],dt[N],ls[N]; vectorint init[N]; struct Tree_Array{int t[N];void Change(int x,int val){if(!x) return;while(xm){t[x]val;xlowbit(x);}return;}int Ask(int x){int ans0;while(x){anst[x];x-lowbit(x);}return ans;}int Maxs(){int zAsk(m);int l0,rm;while(lr){int mid(lr)1;if(Ask(mid)z)rmid-1;else lmid1;}return l;} }T; void Top_Sort(){for(int i1;in;i)if(!in[i])q.push(i),top[cnt]i;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;in[y]--;if(!in[y])q.push(y),top[cnt]y;}}return; } void Get_Dis(){for(int i1;in;i){int xtop[i];for(int jls[x];j;ja[j].next){int ya[j].to;ds[y]max(ds[y],ds[x]1);}}for(int in;i1;i--){int xtop[i];for(int j0;jinit[x].size();j){int yinit[x][j];dt[y]max(dt[y],dt[x]1);}}return; } void Solve(){ans2147483647;for(int i1;in;i)T.Change(dt[i],1);for(int k1;kn;k){int xtop[k];T.Change(dt[x],-1);for(int i0;iinit[x].size();i){int yinit[x][i];T.Change(ds[y]dt[x]1,-1);}int zT.Maxs();if(zans) ansz,idx;T.Change(ds[x],1);for(int ils[x];i;ia[i].next){int ya[i].to;T.Change(ds[x]dt[y]1,1);}}return; } int main() {scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);a[i].toy;a[i].nextls[x];ls[x]i;in[y];init[y].push_back(x);}Top_Sort();Get_Dis();Solve();printf(%d %d,id,ans); }
http://www.huolong8.cn/news/30300/

相关文章:

  • 网站集约化建设什么意思戴尔网站建设目标
  • 移动端网站开发前端模板如何免费让网站上线
  • 微商可以做网站推广吗成全视频免费观看在线看搜索
  • 有什么网站有教师招聘考试题目做企业网络推广方案
  • 贵州企业网站建设案例湖南企业名录大全
  • 惠安网站建设费用亚马逊 wordpress
  • 企业网站模板建立流程应用分发平台
  • 昆山seo网站优化软件怎么在手机上做企业网站
  • nodejs 做网站js交件可以免费开店的平台
  • 门头沟区专业网站制作网站建设建设银行官方网站打不开啊
  • 中山做网站服务好ps里新建网站尺寸怎么做
  • 织梦医院网站模板一站式服务大厅官网
  • 怎样给网站做关键词优化记事本怎样做网站
  • 口碑好的福州网站建设网络部署方案
  • 计算机应用技术php网站开发论文网站建设格式
  • 网站建设项目实践山西手动网站建设推广
  • 房地产网站cms徐州网约车
  • 网站建设设计制作包头三个好消息
  • 如何建立网站快捷方式做一个企业网站价格
  • 凉山州城乡规划建设局网站网站后台编辑器
  • 网站优化培训中心网站建设协议书模板 完整版
  • 计算机网站建设职业群wordpress 导航站
  • 设计参考网站推荐彩票网站开发系统如何搭建
  • 泉州做网站联系方式wordpress评论美化插件
  • 重庆seo整站优化设置网站建设教程软件下载
  • 营销型网站建设式球磨机263企业邮箱登录入口手机版
  • 网站监测营销管理网站
  • 做网站一般注册商标哪个类分销系统方案
  • 网站开发有专利吗网上营销网站
  • 牛商网建设的食品网站深圳物流公司收费标准