\(\\\)

Description

---

給出一個食物網，每個生物指向的生物都是它可以捕食的對象，保證是圖是DAG。

如果一個捕食者的所有捕食對象都滅絕了，那么它們也會滅絕。

求每一個動物滅絕之后，有多少個動物會隨之滅絕。

• \(n\le 65534\)

Solution

---

考察建圖思維的好題。

如果我們按照 捕食者\(\to\)捕食對象 的關系連邊，那么我們得到的是一張捕食關系的流向圖，無法判斷反向的影響。

所以要按照 捕食對象\(\to\)捕食者 的關系連邊，得到的是一張能量供應的流向圖。

那么形象的說，每個點都把能量流向出邊指向的點，如果一個點消失了，從他這里流出去的所有能量全都消失。

如果這個時候某些點沒有能量流入，那么這些點就是需要統計到消失點的答案里。

但是只有這些嗎？并不是。因為這些受影響消失的點可能繼續導致一些點消失，后面的答案我們沒有統計。

我們設 \(die_x\) 表示節點 x 如果消失，有連邊的點直接消失的點的個數。

那么我們一個點要累加的，就是所有直接指向的消失的點的個數+這些點的 \(die\) 值。

---

考慮如何求出 \(die\) 值。我們發現這就是能量供應關系的圖的拓撲序。

我們新建一棵樹形結構，父子關系表示，如果父節點消失，子節點必然消失。

首先將這張能量供應圖中所有入度為 \(0\) 的點連向虛擬根節點，代表他們不會因為別的生物滅亡而滅亡。

然后考慮拓撲到一個點時，它應該作為哪個節點的子節點。顯然是它的所有食物在這棵樹上的 \(LCA\)。

因為拓撲，所以他的所有食物必然已經在這個樹上，我們兩兩合并求 \(LCA\) 即可。

因為要找所有在能量供給圖上指向當前點的點，所以我們還要把捕食的圖建出來，便于找食物有哪些。

因為求 \(LCA\) 多次，需要 \(log\) 的復雜度，因為樹的形態是變化的，所以鏈剖和離線算法顯然都不行。

考慮倍增。查找兩兩合并是沒有問題了，但是新插入節點怎么辦？

注意到倍增數組的構造只需要知道父節點，所以在把拓撲到的點插入樹的同時構造一下倍增數組就好了。

因為這個樹的定義，每一個點的答案顯然是子樹大小 \(-1\) 。

Code

---

一直 \(90\) 不知道為什么，后來發現........

在 \(LCA\) 的時候根節點設成了 \(n+1\) ，但是如果倍增的時候深的跳超了，但是另一個是根節點，根據判斷條件并沒有跳超深度，它就會跳到 0 號節點然后 GG....

給 \(n+1\) 號節點設個深度，或者根節點換成 \(0\) 號節點就好啦

#include<cmath> #include<queue> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 70000 #define R register #define gc getchar using namespace std;inline int rd(){int x=0; bool f=0; char c=gc();while(!isdigit(c)){if(c=='-')f=1;c=gc();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}return f?-x:x; }int n,m,tot,hd[N],deg[N],tot2,hd2[N];int t,tot1,d[N],hd1[N],f[N][20],ans[N];struct edge{int to,nxt;}e[N<<3],e1[N<<1],e2[N<<3];inline void add(int u,int v){e[++tot].to=v; e[tot].nxt=hd[u]; hd[u]=tot; }inline void add1(int u,int v){e1[++tot1].to=v; e1[tot1].nxt=hd1[u]; hd1[u]=tot1; }inline void add2(int u,int v){e2[++tot2].to=v; e2[tot2].nxt=hd2[u]; hd2[u]=tot2; }inline void getfa(int u,int fa){f[u][0]=fa; d[u]=d[fa]+1;for(R int i=1;i<=t;++i) f[u][i]=f[f[u][i-1]][i-1]; }inline int lca(int u,int v){if(d[u]>d[v]) u^=v^=u^=v;for(R int i=t;~i;--i) if(d[f[v][i]]>=d[u]) v=f[v][i];if(u==v) return u;for(R int i=t;~i;--i)if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];return f[u][0]; }inline void work(int u){int res=e2[hd2[u]].to;for(R int i=e2[hd2[u]].nxt;i;i=e2[i].nxt) res=lca(res,e2[i].to);getfa(u,res); add1(u,res); add1(res,u); }void dfs(int u,int fa){for(R int i=hd1[u],v;i;i=e1[i].nxt)if((v=e1[i].to)!=fa){dfs(v,u); ans[u]+=ans[v];} }queue<int> q;int main(){t=log2(n=rd())+1;for(R int i=1,x;i<=n;++i){x=rd();while(x){++deg[i];add(x,i);add2(i,x);x=rd();}ans[i]=1;}for(R int i=1;i<=n;++i)if(!deg[i]){q.push(i); getfa(i,0);add1(i,0); add1(0,i);}while(!q.empty()){int u=q.front(); q.pop();for(R int i=hd[u],v;i;i=e[i].nxt)if((--deg[v=e[i].to])==0) q.push(v),work(v);}dfs(0,-1);for(R int i=1;i<=n;++i) printf("%d\n",ans[i]-1);return 0; }

轉載于:https://www.cnblogs.com/SGCollin/p/9949158.html

總結

以上是生活随笔為你收集整理的[ ZJOI 2012 ] 灾难的全部內容，希望文章能夠幫你解決所遇到的問題。

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