Description

戰狂也在玩《魔方王國》。他只會征兵而不會建城市，因此他決定對小奇的城市進行轟炸。
小奇有n 座城市，城市之間建立了m 條有向的地下通道。戰狂會發起若干輪轟炸，每輪可以轟炸任意多個城市。
每座城市里都有戰狂部署的間諜，在城市遭遇轟炸時，它們會通過地下通道撤離至其它城市。非常不幸的是，在地道里無法得知其它城市是否被轟炸，如果存在兩個不同的城市i，j，它們在同一輪被轟炸，并且可以通過地道從城市i 到達城市j，那么城市i 的間諜可能因為撤離到城市j 而被炸死。為了避免這一情況，戰狂不會在同一輪轟炸城市i 和城市j。
你需要求出戰狂最少需要多少輪可以對每座城市都進行至少一次轟炸。

Input

第一行兩個整數n，m。接下來m 行每行兩個整數a，b 表示一條從a 連向b的單向邊。

Output

輸出一行僅一個整數表示答案。

Sample Input

5 4
1 2
2 3
3 1
4 5

Sample Output

3

Data Constraint

對于20%的數據，n,m<=10。
對于40%的數據，n,m<=1000。
對于另外30%的數據，保證無環。
100%的數據，n,m<=1000000。

Solution

• 這題的描述真的不清楚啊！“到達”指的不是相鄰邊，而是“能通過一些邊到達”。

• 那么顯然一個強連通分量中所需的步數就是其總點數！

• 于是我們先用 tarjan 算法 縮環為點 ，這個點的權值就是其點數。

• 這樣原圖就變成一個 DAG ，為了知道最小輪數，則跑一遍最長路即可.

• 因為肯定是分層地跑最優，于是用拓撲排序的方式實現即可（注意點權為強聯通分量點數）。

• 而且由于 N 比較大（106） ，tarjan 算法需要用人工棧。

• 時間復雜度 O(N) 。

Code

#include<cstdio> using namespace std; const int N=1e6+1; int tot,top,num,ans; int first[N],next[N],en[N]; int first1[N],next1[N],en1[N]; int dfn[N],low[N],stack[N],MS[N],r[N]; int f[N],g[N],d[N],q[N],bel[N]; bool bz[N],vis[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } inline void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y; } inline void insert1(int x,int y) {next1[++tot]=first1[x];first1[x]=tot;en1[tot]=y;d[y]++; } inline void tarjan(int x) {MS[MS[0]=1]=x;while(MS[0]){if(!dfn[x=MS[MS[0]]]){dfn[x]=low[x]=++tot;r[stack[++top]=x]=first[x];bz[x]=vis[x]=true;}bool enter=false;for(int i=r[x];i;i=next[i])if(!vis[en[i]]){r[x]=next[i];MS[++MS[0]]=en[i];enter=true;break;}elseif(bz[en[i]]) low[x]=min(low[x],dfn[en[i]]);if(enter) continue;if(dfn[x]==low[x]){num++;do{bel[stack[top]]=num;bz[stack[top--]]=false;}while(stack[top+1]!=x);}low[MS[--MS[0]]]=min(low[MS[MS[0]]],low[x]);} } int main() {int n=read(),m=read();for(int i=1;i<=m;i++){int x=read(),y=read();insert(x,y);}tot=0;for(int i=1;i<=n;i++)if(!vis[i]) tarjan(i);tot=0;for(int i=1;i<=n;i++){g[bel[i]]++;for(int j=first[i];j;j=next[j])if(bel[i]^bel[en[j]]) insert1(bel[i],bel[en[j]]);}int l=0,r=0;for(int i=1;i<=n;i++)if(!d[i]) f[q[++r]=i]=g[i];while(l<r){int x=q[++l];if(!first1[x]) ans=max(ans,f[x]);for(int i=first1[x];i;i=next1[i]){f[en1[i]]=max(f[en1[i]],f[x]+g[en1[i]]);if(!--d[en1[i]]) q[++r]=en1[i];}}printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5452. 【NOIP2017提高A组冲刺11.5】轰炸的全部內容，希望文章能夠幫你解決所遇到的問題。

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