P4017 最大食物鏈計數
題目來源-洛谷
題意
要求最長食物鏈的數量。按照題意，最長食物鏈就是指有向無環圖DAG中入度為０到出度為０的不同路徑的數量（鏈數）
思路
-
在計算時，明顯：一個被捕食者所在節點的食物鏈路徑是其所有捕食者的路徑條數之和，要計算k節點所在的鏈數，必須清楚其所有入度節點的鏈數。即存在拓撲排序
-
因此借助拓撲排序的方法：計算所有食物鏈數量＝計算每個食物鏈終點的節點（出度為０的節點）的路徑樹之和
-
建立隊列，所有入度為０的節點入隊，初始值為１
-
遍歷，取出隊首元素ｋ節點，遍歷其相鄰的子節點（被捕食者），讓其子節點的食物鏈數量值得＋ｋ節點的數，并讓其子節點入度為－１。若該節點入度為0則推入隊。
-
重復第二遍操作
-
遍歷所有出度為0 的節點（說明這些這些節點所在的最大鏈不會完全相交-是相對獨立的食物鏈），例如5和6兩個節點
-
數據約束
注意數組范圍即可
參考代碼
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int m,n;//n個點m條邊
vector<int> p[MAXN];//鄰接表存圖
int rd[MAXN],cd[MAXN];
queue<int> q;
int ans[MAXN],num = 0;
int main(){ int x,y;cin>>n>>m;for(int i=0;i<m;i++){cin>>x>>y;p[x].push_back(y);cd[x]++;//出度+1 -作為捕食者 rd[y]++;//入度+1 作為被捕食者 }//拓撲排序 //從食物鏈的起點 即入度為0的點for(int i=1;i<=n;i++) {if(rd[i] == 0){q.push(i);ans[i] = 1;//初始鏈設為1 }}while(!q.empty()){int t = q.front();q.pop();for(int i=0;i<p[t].size();i++){int k = p[t][i];//遍歷到的節點設置為k ans[k] = (ans[t]+ans[k])%80112002 ;//食物鏈相加 rd[k] --; //該鏈計算過了 if(rd[k]==0){ //作為捕食者 q.push(k);}}}//遍歷找出度為0的點-說明是已經找到了食物鏈的終點 for(int i=1;i<=n;i++){if(cd[i]==0){num = (num+ ans[i])%80112002;//所有不相交的食物鏈加起來 }} cout<<num; return 0;
}
)
