题目大意：给定一张拓扑图，要求删掉一个点使最长链最小，求删掉的点以及删掉后的最长链
这题真是神思路- –
首先我们建立源点和汇点 源点连向所有点 所有点连向汇点
那么图中最长链就变成了S到T的最长链
然后我们拓扑序DP求出S到每个点的最长链f[x]和每个点到T的最长链g[x]
我们令一条x->y的边的权值为f[x]+g[y]
那么这个图的最长链就转化成了所有边的边权的最大值
更进一步说 是这个图的一个割集中边权的最大值
那么我们的思路基本确定了：枚举删哪个点，用一些数据结构维护删点后割集中点权最大的边
但是这个怎么维护呢？
按照拓扑序删点就行了
令初始S集只有S 所有点和T都在T集
按照拓扑序依次将每个点从T集中删掉，加入S集
首先将这个点的所有入边从数据结构中删掉 此时割集的边权最大值就是删掉这个点的答案
然后再将这个点的所有出边加入数据结构中即可。
至于这个数据结构用什么。。。支持插入，，删除，查询最大值，显然用堆就可以了。
跪Gromah，跪Claris
什么？你问我堆怎么删除？……
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 1001001using namespace std;struct abcd{int to,next;}table[M<<1];int head[M],_head[M],tot;int n,m,ans,ans_len=0x3f3f3f3f;int degree[M],a[M],f[M],g[M];void Add(int head[],int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}namespace Heap{int heap[M],mark[M],top;void Insert(int x){if(mark[x]){–mark[x];return ;}heap[++top]=x;int t=top;while(t>1){if(heap[t]>heap[t>>1])swap(heap[t],heap[t>>1]),t>>=1;elsebreak;}}void Delete(int x){mark[x]++;}void Pop(){heap[1]=heap[top–];int t=2;while(t<=top){if( t<top && heap[t+1]>heap[t] )t++;if(heap[t]>heap[t>>1])swap(heap[t],heap[t>>1]),t<<=1;elsebreak;}}int Top(){while(mark[heap[1]])mark[heap[1]]–,Pop();return heap[1];}}void Topology_Sort(){static int q[M],r,h;int i;for(i=1;i<=n;i++)if(!degree[i])q[++r]=i;while(r!=h){int x=q[++h];for(i=head[x];i;i=table[i].next)if(!–degree[table[i].to])q[++r]=table[i].to;}memcpy(a,q,sizeof a);}int main(){using namespace Heap;int i,j,x,y;cin>>n>>m;for(i=1;i<=m;i++){scanf("%d%d",&x,&y);degree[y]++;Add(head,x,y);Add(_head,y,x);}Topology_Sort();for(j=1;j<=n;j++){x=a[j];f[x]=max(f[x],1);for(i=head[x];i;i=table[i].next)f[table[i].to]=max(f[table[i].to],f[x]+1);}for(j=n;j;j–){x=a[j];g[x]=max(g[x],1);for(i=head[x];i;i=table[i].next)g[x]=max(g[x],g[table[i].to]+1);}for(i=1;i<=n;i++)Insert(g[i]);Insert(0);for(j=1;j<=n;j++){x=a[j];for(i=_head[x];i;i=table[i].next)Delete(f[table[i].to]+g[x]);Delete(g[x]);if(Top()<ans_len)ans_len=Top(),ans=x;for(i=head[x];i;i=table[i].next)Insert(f[x]+g[table[i].to]);Insert(f[x]);}cout<<ans<<' '<<ans_len-1<<endl;return 0;}
问：一只小狗在沙漠中旅行，结果死了，问他是怎么死的？
