題目鏈接

BZOJ3832

題解

神思路orz，根本不會做

設\(f[i]\)為到\(i\)的最長路，\(g[i]\)為\(i\)出發的最長路，二者可以拓撲序后\(dp\)求得
那么一條邊\((u,v)\)的對應的最長鏈就是\(f[u] + 1 + g[v]\)
我們人為加入源匯點\(S\)，\(T\)，\(S\)向每個點連邊，每個點向\(T\)連邊
我們考慮把整個圖劃分開
一開始所有點都在\(T\)這邊，割邊為所有\(S\)的邊
然后我們按照拓撲序把點逐一加入\(S\)集合中
加入時，我們刪去\(S\)集合連向該點的邊，然后詢問所有邊的最大值，即為刪去該點的最長鏈
加入后，我們加入該點連向\(T\)集合的邊
由于是按照拓撲序，所以以上提到的所有邊就是該點的所有入邊/出邊

然后所有邊的最大值可以用堆或者線段樹維護

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<cmath> #include<map> #define Redge(u) for (int k = h[u]; k; k = ed[k].nxt) #define REP(i,n) for (int i = 1; i <= (n); i++) #define mp(a,b) make_pair<int,int>(a,b) #define cls(s) memset(s,0,sizeof(s)) #define cp pair<int,int> #define LL long long int using namespace std; const int maxn = 500005,maxm = 2000005,INF = 1000000000; inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag; } struct Heap{priority_queue<int> a,b;void ck(){while (!b.empty() && a.top() == b.top()) a.pop(),b.pop();}int size(){return a.size() - b.size();}void ins(int x){ck(); a.push(x);}void del(int x){ck(); b.push(x);}int top(){ck(); return size() ? a.top() : 0;} }H; int n,m,f[maxn],g[maxn],s[maxn]; int q[maxn],head,tail; int h[maxn],de[maxn],ne; int hi[maxn],nei; struct EDGE{int to,nxt;}ed[maxm],e[maxm]; inline void build(int u,int v){ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;de[v]++;e[++nei] = (EDGE){u,hi[v]}; hi[v] = nei; } void topu(){head = 0; tail = -1; int u;REP(i,n) if (!de[i]) q[++tail] = i;REP(i,n){s[i] = u = q[head++];Redge(u) if (!(--de[ed[k].to])) q[++tail] = ed[k].to;} } void init(){REP(i,n){int u = s[i];Redge(u) f[ed[k].to] = max(f[ed[k].to],f[u] + 1);}for (int i = n; i; i--){int u = s[i];Redge(u) g[u] = max(g[u],g[ed[k].to] + 1);} } void solve(){int ans = INF,ansu = 0,x;REP(i,n) H.ins(g[i]);REP(i,n){int u = s[i];H.del(g[u]);for (int k = hi[u]; k; k = e[k].nxt)H.del(f[e[k].to] + 1 + g[u]);x = H.top();if (x < ans) ans = x,ansu = u;H.ins(f[u]);Redge(u) H.ins(f[u] + 1 + g[ed[k].to]);}printf("%d %d\n",ansu,ans); } int main(){n = read(); m = read();int a,b;REP(i,m){a = read(); b = read();build(a,b);}topu();init();//REP(i,n) printf("node%d f = %d g = %d\n",i,f[i],g[i]);solve();return 0; }

轉載于:https://www.cnblogs.com/Mychael/p/9097788.html

總結

以上是生活随笔為你收集整理的BZOJ3832 [Poi2014]Rally 【拓扑序 + 堆】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。