博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【BZOJ】3832: [Poi2014]Rally
阅读量:6623 次
发布时间:2019-06-25

本文共 1836 字,大约阅读时间需要 6 分钟。

题意

\(n(2 \le n \le 500000)\)个点\(m(1 \le m \le 1000000)\)条边的有向无环图,找到一个点,使得删掉这个点后剩余图中的最长路径最短。

分析

神题不会做。

题解

首先我们新建个源\(s\)和汇\(t\),连边\(s->i, i->t\),最远距离分别为\(d[i, 0]\)\(d[i, 1]\),则一个图中的最长链就是\(max(d[u, 0]+d[v, 1]-1, \exists edge(u, v))\),再由于图中任意一个\(s-t\)割都会有最长链的边,那么问题就转化为去掉\(x\)点及其相关的边后,在途中的一个割中找最大值。由于图是拓扑序的,所以,我们只要把某割点的入边拿掉后、拓扑秩在自己前或相同的点出边都加入到一个堆里,那么堆中就可以形成一个割!这个比较显然。

#include 
using namespace std;inline int getint() { int x=0; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()); for(; c>='0'&&c<='9'; x=x*10+c-'0', c=getchar()); return x;}const int N=500005;int q[N], in[N], d[N][2], n, cnt1, cnt2, ihead1[N], ihead2[N], sz[N<<2];struct E { int next, to;}e1[N<<2], e2[N<<2];void add(int x, int y) { e1[++cnt1]=(E){ihead1[x], y}; ihead1[x]=cnt1; e2[++cnt2]=(E){ihead2[y], x}; ihead2[y]=cnt2; ++in[y];}void ins(int p, int d, int l=0, int r=n, int x=1) { sz[x]+=d; if(l==r) { return; } int mid=(l+r)>>1; p<=mid?ins(p, d, l, mid, x<<1):ins(p, d, mid+1, r, x<<1|1);}int ask(int l=0, int r=n, int x=1) { if(l==r) { return l; } int mid=(l+r)>>1, ls=x<<1, rs=ls|1; return sz[rs]?ask(mid+1, r, rs):ask(l, mid, ls);}int main() { n=getint(); int m=getint(), fr=0, ta=0; for(int i=1; i<=m; ++i) { int x=getint(), y=getint(); add(x, y); } for(int i=1; i<=n; ++i) { if(!in[i]) { q[ta++]=i; } } while(fr!=ta) { int x=q[fr++]; for(int i=ihead1[x]; i; i=e1[i].next) { if(!--in[e1[i].to]) { q[ta++]=e1[i].to; } } } for(int j=0; j
(t=ask())) { ans1=x; ans2=t; } for(int i=ihead1[x]; i; i=e1[i].next) { ins(d[x][0]+d[e1[i].to][1]+1, 1); } } printf("%d %d\n", ans1, ans2); return 0;}

转载地址:http://odtpo.baihongyu.com/

你可能感兴趣的文章
sqlserver2005群集
查看>>
IBM_System_x3650服务器固件升级手顺
查看>>
freemarker判断对象是否为空
查看>>
Iptables
查看>>
awk单行脚本
查看>>
Memcached Server High availability
查看>>
CentOS6.6 部署LAMP系统架构
查看>>
C语言基于GTK+Libvlc实现的简易视频播放器
查看>>
Solr API例子详解
查看>>
软件开发之通病解析
查看>>
Ubuntu下编译安装vim/gvim 8.0
查看>>
python wxPython 5 (框架 wx.Frame)
查看>>
windows server backup 功能备份虚拟机
查看>>
zookeeper 客户端
查看>>
我的友情链接
查看>>
还不错的上传文件的Django实现
查看>>
将一个函数在主线程执行的4种方法
查看>>
如何在pcDuino Ubuntu上看带Flash的网站
查看>>
(转载)Hive学习笔记--Hive 原理
查看>>
Go1.2新功能简介
查看>>