拓扑排序 堆

洛谷题目传送门 BZOJ题目传送门

妙蛙

注意到这是一个DAG，那么我们可以一遍拓排求出从起点到$i$为最长路$ds[i]$和$i$到终点的最长路$dt[i]$（s向所有入度为0的点连边，所有出度为0的点向t连边）。若一条最长路$l$经过$(u,v)$，那么必有$l=ds[u]+dt[v]+1$。

我们按照拓扑序枚举每个点。每次把关于它的最长路从$t$集删掉并更新答案，然后把它们加到$s$集里。因此要维护的就是三个操作：删除一个数，插入一个数和查询最大值。用堆即可。

代码：

#include<queue> #include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define N 500005 #define F inline using namespace std; struct edge{ int nxt,to; }ed[N<<1]; int n,m,k,h1[N],h2[N],ds[N],dt[N],in[N],que[N]; struct Queue{ priority_queue <int> q,d; F void push(int x){ q.push(x); } F void erase(int x){ d.push(x); } F void pop(){ while (!d.empty()&&q.top()==d.top()) q.pop(),d.pop(); q.pop(); } F int top(){ while (!d.empty()&&q.top()==d.top()) q.pop(),d.pop(); return q.top(); } }q; F char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); return l==r?EOF:*l++; } F int _read(){ int x=0; char ch=readc(); while (!isdigit(ch)) ch=readc(); while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc(); return x; } F void tp(){ int l=0,r=0; for (int i=1;i<=n;i++) if (!in[i]) que[++r]=i; while (l<r) for (int x=que[++l],i=h1[x];i;i=ed[i].nxt) if (!(--in[ed[i].to])) que[++r]=ed[i].to; for (int i=1;i<=n;i++) for (int x=que[i],j=h1[x];j;j=ed[j].nxt) ds[ed[j].to]=max(ds[ed[j].to],ds[x]+1); for (int i=n;i;i--) for (int x=que[i],j=h2[x];j;j=ed[j].nxt) dt[ed[j].to]=max(dt[ed[j].to],dt[x]+1); } #define add(h,x,y) ed[++k]=(edge){h[x],y},h[x]=k int main(){ n=_read(),m=_read(); for (int i=1,x,y;i<=m;i++) x=_read(),y=_read(),add(h1,x,y),add(h2,y,x),in[y]++; tp(); int id,ans=2e9; for (int i=1;i<=n;i++) q.push(dt[i]); for (int i=1;i<=n;i++){ int x=que[i]; q.erase(dt[x]); for (int j=h2[x];j;j=ed[j].nxt) q.erase(ds[ed[j].to]+dt[x]+1); if (q.top()<ans) ans=q.top(),id=x; for (int j=h1[x];j;j=ed[j].nxt) q.push(ds[x]+dt[ed[j].to]+1); q.push(ds[x]); } return printf("%d %d",id,ans),0; }