题意 ：
给定一个DAG，问去掉一个点后最长路径长度最短是多少。
---------------此后一千里--------------------------
先%一发
神奇的思路
我们考虑将整个图topo排序一下，处理出到每个点的最长路径长度f[i]和每个点出发的最长路径长度g[i]
那么对于图上的一条可能最长路径，我们就可以表示成f[i]+g[j]，然后我们可以把这个值赋给i->j的边上
问题就变成了去掉一个点，原图割集的边权与割开部分边权的最大值
我们先假设所有点都在T集合里，那么割集是没有边的，我们只用管T集里的边权，就可以把所有点的g丢到堆里
我们如果删除一个点，我们可以把它从T集里删去，对T集边权影响是去掉这个点的g值，对割集影响是去掉这个点与S集连边的权值
恢复时把这个点丢到S集去，影响和删除差不多
我们怎么样方便的去维护上面这些东西呢?
可以按topo序去维护
因为如果乱丢的话，你丢掉的点可能会影响在T集里的点的g值，就会出错，而如果按topo序丢，可以保证你丢的这个点不会影响仍在T集里的点的g，而且可以保证直接连向这个点的点都在S集里，就可以方便地维护上面的信息了
至于为什么恢复时要丢到S集去，因为在S集里我们关心的是点的f值，你之后删除别的点对之前点的f值是没有影响的，而对g值有影响
代码 ：
#include<bits/stdc++.h> using namespace std; inline int Max(int a,int b) {return a>b?a:b;} inline int Min(int a,int b) {return a<b?a:b;} #define MAXN 500005 int n,m,ans=MAXN+5,ans1; int head[MAXN][2],cnt,deg[MAXN][2];bool vis[MAXN][2]; struct Edge{ int to,next; }e[MAXN*4]; inline void insert(int a,int b,int p) { deg[a][p]++; e[++cnt].next=head[a][p];head[a][p]=cnt;e[cnt].to=b; } int f[MAXN],g[MAXN],tp[MAXN][2]; void topo(int v,int p) { tp[++tp[0][p]][p]=v;vis[v][p]=1; for(int i=head[v][p^1];i;i=e[i].next) if(--deg[e[i].to][p]==0&&!vis[e[i].to][p]) topo(e[i].to,p); } priority_queue<int> q,d; int main() { scanf("%d%d",&n,&m); for(int a,b,i=1;i<=m;i++) { scanf("%d%d",&a,&b); insert(a,b,1);insert(b,a,0); } for(int i=1;i<=n;i++) { if(!deg[i][0]&&!vis[i][0]) topo(i,0); if(!deg[i][1]&&!vis[i][1]) topo(i,1); } for(int i=1;i<=n;i++) { int a=tp[i][1],b=tp[i][0]; for(int j=head[a][1];j;j=e[j].next) g[a]=Max(g[a],g[e[j].to]); for(int j=head[b][0];j;j=e[j].next) f[b]=Max(f[b],f[e[j].to]); g[a]++;f[b]++; } for(int i=1;i<=n;i++) q.push(g[i]); for(int i=1;i<=n;i++) { int k=tp[i][0]; for(int j=head[k][0];j;j=e[j].next) d.push(f[e[j].to]+g[k]); d.push(g[k]); while(!d.empty()&&!q.empty()&&d.top()==q.top()) q.pop(),d.pop(); if(q.top()<ans) {ans=q.top();ans1=k;} for(int j=head[k][1];j;j=e[j].next) q.push(f[k]+g[e[j].to]); q.push(f[k]); } printf("%d %d ",ans1,ans-1); return 0; }