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。
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<ext/pb_ds/priority_queue.hpp>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int inf=0x7fffffff;
const int V=,E=;
struct Edge {
int from,to;
};
Edge e[E];
int w[E];
int s,t;
int n,m;
std::vector<int> eids[V],eidt[V];
int inds[V]={},indt[V]={};
inline void add_edge(const int u,const int v,int *ind,std::vector<int> *eid,const int i) {
eid[u].push_back(i);
ind[v]++;
}
int diss[V]={},dist[V]={};
std::queue<int> top;
inline void Kahn(const int s,std::vector<int> *eid,int *dis,int *ind,const int op=) {
std::queue<int> q;
q.push(s);
while(!q.empty()) {
int x=q.front();
q.pop();
if(op) top.push(x);
for(register unsigned i=;i<eid[x].size();i++) {
int y=e[eid[x][i]].from^e[eid[x][i]].to^x;
dis[y]=std::max(dis[y],dis[x]+);
if(!--ind[y]) q.push(y);
}
}
}
__gnu_pbds::priority_queue<int> q;
__gnu_pbds::priority_queue<int>::point_iterator p[E];
int v,ans=inf;
int cnt=;
inline void solve() {
while(!top.empty()) {
int x=top.front();
top.pop();
for(register unsigned i=;i<eidt[x].size();i++) {
q.erase(p[eidt[x][i]]);
}
if(!q.empty()) {
if((x!=s)&&(x!=t)&&(q.top()<ans)) {
ans=q.top();
v=x;
}
}
for(register unsigned i=;i<eids[x].size();i++) {
p[eids[x][i]]=q.push(w[eids[x][i]]);
}
}
}
int main() {
n=getint(),m=getint();
s=,t=n+;
for(register int i=;i<=n;i++) {
e[cnt].from=s,e[cnt].to=i;
add_edge(s,i,inds,eids,cnt);
add_edge(i,s,indt,eidt,cnt);
cnt++;
}
for(register int i=;i<m;i++) {
int &u=e[cnt].from=getint(),&v=e[cnt].to=getint();
add_edge(u,v,inds,eids,cnt);
add_edge(v,u,indt,eidt,cnt);
cnt++;
}
for(register int i=;i<=n;i++) {
e[cnt].from=i,e[cnt].to=t;
add_edge(i,t,inds,eids,cnt);
add_edge(t,i,indt,eidt,cnt);
cnt++;
}
Kahn(s,eids,diss,inds,);
Kahn(t,eidt,dist,indt);
for(register int i=;i<cnt;i++) {
w[i]=diss[e[i].from]+dist[e[i].to]-;
}
solve();
printf("%d %d\n",v,ans);
return ;
}