P3573 [POI2014]RAJ-Rally
2024-08-30 21:11:02
很妙的思路
首先这是一个DAG,于是我们先在原图和反图上各做一遍,分别求出\(diss_i\)和\(dist_i\)表示从\(i\)点出发的最短路和以\(i\)为终点的最短路
我们考虑把点分为两个集合\(S\)和\(T\),一开始所有的点都在\(T\)中,按照拓扑序依次将点从\(T\)中取出放入\(S\)
考虑对于点\(u\),它从\(T\)中被取出,我们把它看做删除了这个点。那么这时图中的最长路径必定属于以下三种中的一种
1.\(S\)中最大的\(dist_i\)
2.\(T\)中最大的\(diss_i\)
3.\(dist_i+diss_j+1\),其中\(i\)在\(S\)中,\(j\)在\(T\)中
于是我们只要能够维护好这些东西就可以了。将\(u\)从\(T\)中取出时,把它的\(diss_u\)删去,并把所有的\(dist_v+diss_u+1\)也删去(\(v\)表示所有有边指向\(u\)的点),这时的最大值即为删掉点\(u\)时图中的最长路。把它新加入\(S\)中时,加入它的\(dist_u\),以及所有的\(diss_u+dist_v+1\)(\(v\)表示\(u\)指向的所有点)
以上操作可以用线段树来维护
//minamoto
#include<bits/stdc++.h>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
int read(){
int res,f=1;char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
const int N=1e6+5;
int head[N],Next[N],ver[N],du[N],tot;
int hc[N],nc[N],vc[N],tc;
inline void add(int u,int v){ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}
inline void addc(int u,int v){vc[++tc]=v,nc[tc]=hc[u],hc[u]=tc;}
int diss[N],dist[N],q[N],n,m,ans=0x3f3f3f3f,id,mx;
void topo(){
int h=1,t=0;
for(int i=1;i<=n;++i)if(!du[i])q[++t]=i;
while(h<=t){
int u=q[h++];
for(int i=head[u];i;i=Next[i]){
cmax(dist[ver[i]],dist[u]+1);
if(--du[ver[i]]==0)q[++t]=ver[i];
}
}
for(int j=n;j;--j){
int u=q[j];
for(int i=head[u];i;i=Next[i])cmax(diss[u],diss[ver[i]]+1);
}
}
#define ls (p<<1)
#define rs (p<<1|1)
int sum[N<<2];
void upd(int p,int l,int r,int x,int v){
if(l==r)return (void)(sum[p]+=v);
int mid=(l+r)>>1;
x<=mid?upd(ls,l,mid,x,v):upd(rs,mid+1,r,x,v);
sum[p]=sum[ls]+sum[rs];
}
int query(int p,int l,int r){
if(l==r)return l;int mid=(l+r)>>1;
return sum[rs]?query(rs,mid+1,r):query(ls,l,mid);
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),m=read();
for(int i=1,u,v;i<=m;++i)u=read(),v=read(),add(u,v),addc(v,u),++du[v];
topo();for(int i=1;i<=n;++i)upd(1,0,n,diss[i],1);
for(int j=1;j<=n;++j){
int u=q[j];upd(1,0,n,diss[u],-1);
for(int i=hc[u];i;i=nc[i])upd(1,0,n,diss[u]+dist[vc[i]]+1,-1);
if((mx=query(1,0,n))<ans)ans=mx,id=u;
for(int i=head[u];i;i=Next[i])upd(1,0,n,dist[u]+diss[ver[i]]+1,1);
upd(1,0,n,dist[u],1);
}
printf("%d %d\n",id,ans);return 0;
}
最新文章
- iPhone CSS media query(媒体查询)
- hdu5255 魔法因子
- ExtJs布局大全
- 矩阵快速幂(入门) 学习笔记hdu1005, hdu1575, hdu1757
- 修改tomcat访问路径
- Oracle + EF5 疑难杂症
- jpg图片在开发板上显示
- angular : direative : autoResize textarea auto resize
- HTML5—canvas绘制图形(1)
- iOS下KVO使用过程中的陷阱 (转发)
- centos7服务器配置nuxt部署环境
- 关于HttpClient上传中文乱码的解决办法
- 十分钟搞定 pandas
- pymsql简单的使用
- 在类文件中创建 写入Json文件
- log4net使用的两种方式
- 苹果cms安装及配置详细教程
- 【Noip模拟 20160929】树林
- 002.Heartbeat部署及httpd高可用
- 家庭记账本之微信小程序(一)
热门文章
- PS学习笔记(05)
- 【Codeforces 1042D】Petya and Array
- Flask(4):wtforms组件 &; 数据库连接池 DBUtils
- 【HDOJ3341】Lost&#39;s revenge(AC自动机,DP)
- 打开Eclipse出现“An internal error has occurred. java.lang.NullPointerException
- html5 编辑
- 如何使用python书写守护进程?daemon、python-daemon
- Django学习系列之Form验证
- java.lang.IllegalArgumentException: sheetName &;#39;&;#39; is invalid
- 仰视源代码,实现strcmp