OJ题号：
BZOJ3832、洛谷3573思路：
建立超级源汇$S$和$T$，DP求出分别以$S$和$T$为源点的最长路$diss$和$dist$。
对于每条边$i$，设定一个权值$w_i=diss_{i.from}+dist_{i.to}-1$。 表示原图中包含这条边的从$S$到$T$的最长路。 然后按照拓扑序删点$x$，用堆维护不包含$x$的最长路长度。 然而一次性不能把所有边放进去，不然会MLE一个点（因为这个调了一个晚上）。 应该在换$x$的时候，把老$x$的出边重新加入，并将新$x$的入边删去。 注意开的数组不能太多，能合并的信息尽量合并，（比如所有边正反边用一个数组存，取值的时候用异或），不然把堆修改以后还是会MLE。1 #include2 #include 3 #include 4 #include 5 #include 6 inline int getint() { 7 register char ch; 8 while(!isdigit(ch=getchar())); 9 register int x=ch^'0';10 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');11 return x;12 }13 const int inf=0x7fffffff;14 const int V=500002,E=2000000;15 struct Edge {16 int from,to;17 };18 Edge e[E];19 int w[E];20 int s,t;21 int n,m;22 std::vector eids[V],eidt[V];23 int inds[V]={ 0},indt[V]={ 0};24 inline void add_edge(const int u,const int v,int *ind,std::vector *eid,const int i) {25 eid[u].push_back(i);26 ind[v]++;27 }28 int diss[V]={ 0},dist[V]={ 0};29 std::queue top;30 inline void Kahn(const int s,std::vector *eid,int *dis,int *ind,const int op=0) {31 std::queue q;32 q.push(s);33 while(!q.empty()) {34 int x=q.front();35 q.pop();36 if(op) top.push(x);37 for(register unsigned i=0;i