[문제 풀이] [LG - P3573] [POI 2014] RAJ - Plaly

f (u) f (u) f (u) 를 설정 하면 노드 u u 에서 출발 하 는 가장 긴 길 을 표시 하고 g (u) g (u) g (u) g (u) 는 u u 가 끝 나 는 가장 긴 길 을 표시 합 니 다. 이 두 d p dp 의 이전 은 모두 비교적 뚜렷 하 므 로 말 하지 않 겠 습 니 다.그러면 한 변 (u, v) (u, v) (u, v) 을 지나 가 는 가장 긴 길 은 g (u) + 1 + f (v) g (u) + 1 + f (v) g (u) + 1 + f (v) 이다.
o r d u ord 로u ordu 는 노드 u u 의 토폴로지 순 서 를 나타 낸다.
한 노드 u u u 를 삭제 한 후에 우 리 는 노드 를 토폴로지 순서에 따라 두 부분 으로 나 누 었 다. A, B A, B. 그 중에서 A A 의 노드 의 토폴로지 순 서 는 o r d u ord 보다 작다.u ordu 의, B B B 중 노드 의 토폴로지 순 서 는 모두 o r d u ord 보다 크다.u ordu 의.
그러면 답 은 분명히 세 가지 상황 만 선택 할 수 있다.

A A A 내부 의, 즉 max * 8289 ° u * 8712 ° A {g (u)} \ max \ limits{u \in A} \{ g(u) \} u∈Amax​{ g(u)}。

B B B B 내부 의, max * 8289 ° u * 8712 ° B {f (u)} \ \ max \ limits{u \in B} \{f(u)\} u∈Bmax​{ f(u)}。

A A A 가 B B B 에 연 결 된, max ⁡ (u, v) 8712 ° E, u 8712 ° A, v 8712 ° B {g (u) + 1 + f (v)} \ \ max \ \ limits{(u,v) \in E, u \in A, v \in B} \{g(u)+1+f(v)\} (u,v)∈E,u∈A,v∈Bmax​{ g(u)+1+f(v)}

지금 우 리 는 u u 를 삭제 하 는 상황 을 통계 한 후에 정 보 를 u 를 삭제 할 때 까지 업데이트 할 수 있다.  ( o r d u ′ = o r d u + 1 ) u'~(ord_{u'}=ord_{u}+1) u′ (ordu ′ = ordu + 1) 의 경우.이 일 을 완성 하기 위해 서 우 리 는 삭제 할 수 있 는 더미 가 필요 하 다.
처음에 모든 노드 는 B B B 에 있 었 다. 즉, 모든 f (u) f (u) f (u) 를 쌓 아 올 렸 다.이어서 우 리 는 토폴로지 순서에 따라 어 릴 때 부터 어른 이 될 때 까지 노드 u u 의 관련 정 보 를 삭제 한 다음 에 u u 를 A A A 에 넣 는 것 을 고려 했다.
우선 u u 의 정 보 를 삭제 합 니 다.f (u) f (u) f (u) 를 삭제 하고 경과 (v, u) 를 삭제 합 니 다.  ( v ∈ A ) (v,u)~(v\in A) (v,u) (v * 8712 ° A) 의 가장 긴 길 이면 됩 니 다 (안개).
이 어 모든 u u 의 정 보 를 추가 하고 먼저 g (u) g (u) g (u) 를 추가 한 다음 에 경과 (u, v) 를 추가 합 니 다.  ( v ∈ B ) (u,v)~(v\in B) (u,v) (v * 8712 ° B) 의 가장 긴 길.
그러면 최종 코드 는 다음 과 같다.

#include 

using namespace std;

const int maxn = 5e5 + 5, INF = 1e9;
int read_int() {
     
	int t = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while ('0' <= ch && ch <= '9')
		t = (t << 3) + (t << 1) + ch - '0',
		ch = getchar();
	return t;
}
int n;
struct Graph {
     
	struct Edge {
     
		int v, nex;
		Edge(int v = 0, int nex = 0) : v(v), nex(nex) {
     }
	} E[maxn << 1];
	int hd[maxn], deg[maxn], tote;
	void addedge(int u, int v) {
     
		E[++tote] = Edge(v, hd[u]), hd[u] = tote, deg[v]++;
	}

	int ls[maxn], ls_sz, f[maxn];
	queue<int> q;
	void topo() {
     
		for (int i = 1; i <= n; i++) if (!deg[i]) q.push(i);
		while (!q.empty()) {
     
			int u = q.front(); q.pop(), ls[++ls_sz] = u;
			for (int i = hd[u]; i; i = E[i].nex) {
     
				int v = E[i].v;
				deg[v]--;
				if (!deg[v]) q.push(v);
			}
		}
		for (int p = n; p >= 1; p--) {
     
			int u = ls[p];
			for (int i = hd[u]; i; i = E[i].nex)
				f[u] = max(f[u], f[E[i].v] + 1);
		}
	}
} G, rG;

struct RbHeap {
     
	priority_queue<int> q, del_q;
	void push(int val) {
      q.push(val); }
	void pop(int val) {
      del_q.push(val); }
	int top() {
     
		while (del_q.size() && q.top() == del_q.top()) q.pop(), del_q.pop();
		return (q.size() ? q.top() : -INF);
	}
} hp;

int main() {
     
	int m; n = read_int(), m = read_int();
	for (int i = 1; i <= m; i++) {
     
		int u = read_int(), v = read_int();
		G.addedge(u, v), rG.addedge(v, u);
	} 
	G.topo(), rG.topo();
	int ans1, ans2;
	for (int i = 1; i <= n; i++) hp.push(G.f[i]);
	ans2 = hp.top();
	for (int p = 1; p <= n; p++) {
     
		int u = G.ls[p]; hp.pop(G.f[u]);
		for (int i = rG.hd[u]; i; i = rG.E[i].nex) {
     
			int v = rG.E[i].v;
			hp.pop(rG.f[v] + 1 + G.f[u]);
		}
		int val = hp.top();
		if (val < ans2) ans1 = u, ans2 = val;
		hp.push(rG.f[u]);
		for (int i = G.hd[u]; i; i = G.E[i].nex) {
     
			int v = G.E[i].v;
			hp.push(rG.f[u] + 1 + G.f[v]);
		}
	}
	printf("%d %d
", ans1, ans2);
	return 0;
}