最新要闻

广告

手机

成都车展：捷尼赛思X Speedium Coupe

成都车展：捷尼赛思X Speedium Coupe

 宏力医疗管理(09906)发布中期业绩，股东应占利润2426.3万元 同比减少24.6%

宏力医疗管理(09906)发布中期业绩，股东应占利润2426.3万元 同比减少24.6%

家电

  1. 首页
  2. 移动通信
  3. 内容

P4017 最大食物链计数 （DAG拓扑排序）

来源：博客园

空降锣鼓

1 题目分析

首先 ，要知道这道题是 Topo 拓扑排序。不妨先从拓扑排序定义下手，分析题目的性质。经分析得：

食物链中的生物 —— 节点


(资料图片)

生物之间的关系 —— 有向边

为了方便描述，我们将

不会捕食其他生物的 生产者叫做 最佳生产者

不会被其他生物捕食的 消费者叫做 最佳消费者

由于数据中不会出现环，所以 最大食物链即 左端是 最佳生产者，右端是 最佳消费者的路径

而 只要最左端是 最佳生产者的路径（即最右端可以不是 最佳消费者 的最大食物链） 我们称之为 类食物链

既然 食物链中的生物 可以看成 节点，那么 最佳生产者的入度一定为 0，而 最佳消费者的出的也为 0

2 解题思路

想要找到一条 最大食物链 ，那么这条路径的 起点 入度要为0，终点 出度要为0。故：

既要记录入度，还要记录出度！

现在的问题转换成了，如何找到图中所有 左端点入度为0 且 右端点出度为0 的路径的数量

3 题解

#include#define MAXN 5002using namespace std;int n,m,ind[MAXN],outd[MAXN];//顶点数，入度，出度 vectore[MAXN];//邻接表 int num[MAXN];//记录到这个点食物链的数量int mod=80112002;//定义最终答案mod的值 int ans;//记录答案 int main(){cin>>n>>m;queueq;for(int i=1;i<=m;++i){//输入边 int x,y;cin>>x>>y;++ind[y],++outd[x];//右节点入度+1，左节点出度+1e[x].push_back(y);//建立一条单向边 } for(int i=1;i<=n;++i){//初次寻找入度为0的点[最佳生产者] if(!ind[i]){//是最佳生产者 num[i]=1;//初始化 q.push(i);//压入队列 }}while(!q.empty()){//还可以进行topo排序 int tot=q.front();//取出队首q.pop();//弹出int len=e[tot].size();for(int i=0;i

关键词：