23333333orz heheda。
用multiset就可以。这题有些卡空间。
题解推荐POPOQQQ。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<queue> #include<vector> #define maxv 500500 #define maxe 2000050 #define inf 2000000000 using namespace std; int n,m,x,y,g[maxv],f[maxv][3],d[maxv],nume=0,s,t; struct edge { int v,nxt; }e[maxe]; struct pnt { int id,rank; }p[maxv]; multiset <int> st; vector <int> v1[maxv],v2[maxv]; queue <int> q; bool cmp(pnt x,pnt y) { return x.rank<y.rank; } void addedge(int u,int v) { e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume; } void get_path() { q.push(s); p[s].id=s;p[t].id=t;p[s].rank=0; while (!q.empty()) { int head=q.front();q.pop(); for (int i=g[head];i;i=e[i].nxt) { int v=e[i].v; if (!(--d[v])) { q.push(v); p[v].id=v;p[v].rank=p[head].rank+1; } } } sort(p,p+n+2,cmp); for (int i=0;i<=n+1;i++) { int x=p[i].id; for (int j=g[x];j;j=e[j].nxt) { int v=e[j].v; f[v][1]=max(f[v][1],f[x][1]+1); } } for (int i=n+1;i>=0;i--) { int x=p[i].id; for (int j=g[x];j;j=e[j].nxt) { int v=e[j].v; f[x][2]=max(f[x][2],f[v][2]+1); } } } void del(int x) { for (int i=0;i<v2[x].size();i++) { int v=v2[x][i]; st.erase(st.find(f[v][1]+f[x][2]-1)); } } void insert(int x) { for (int i=0;i<v1[x].size();i++) { int v=v1[x][i]; st.insert(f[x][1]+f[v][2]-1); } } void get_ans() { int ans=inf,pos; for (int i=0;i<=n;i++) { if (!st.empty()) { del(p[i].id); int now=*--st.end(); if (now<ans) {ans=now;pos=p[i].id;} else if ((now==ans) && (pos>p[i].id)) pos=p[i].id; } insert(p[i].id); } printf("%d %d ",pos,ans); } int main() { scanf("%d%d",&n,&m);s=0;t=n+1; for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); addedge(x,y);d[y]++;v1[x].push_back(y);v2[y].push_back(x); } for (int i=1;i<=n;i++) { addedge(s,i);addedge(i,t);d[i]++;d[t]++; v1[s].push_back(i);v2[i].push_back(s); v1[i].push_back(t);v2[t].push_back(i); } get_path(); get_ans(); return 0; }