当前位置：首页 > article >正文

洛谷P4017 最大食物链计数（图的拓扑排序）

article 2025/1/20 1:19:41

题目链接：P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态

题目描述

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

由于这个结果可能过大，你只需要输出总数模上 80112002 的结果。

输入格式

第一行，两个正整数 n，m，表示生物种类 n 和吃与被吃的关系数 m。

接下来 m 行，每行两个正整数，表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数，为最大食物链数量模上 80112002 的结果

样例输入：

输出：

解题思路：本题也是用到了拓扑排序，不难想到我们建图可以这样考虑

食物链中的生物看作节点，生物之间的关系建立一条 有向边

为了方便描述，我们将

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

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

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

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

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

思路引导：

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

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

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

下面奉上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 5e5 + 10,MOD = 80112002; 

int n,m;
int h[N],e[N],ne[N], idx;//邻接表存图 
int q[N],s[N]; 
int in[N],out[N];//in表示入度,out表示出度 

void add(int a,int b)//建立一条从a指向b的边 
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void topsort()//拓扑排序 
{
	int hh = 0,tt = -1;
	
	for(int i = 1; i <= n; i++)//将度数为0的点插入队列 
    {
    	if(!in[i]) {//初始化方案数
    		q[++tt] = i;
    		s[i] = 1;
		} 
	}
	
	while(hh <= tt)
	{
		int t = q[hh++];//取出队头 
		
		for(int i = h[t]; i != -1; i = ne[i])//遍历所有边 
		{
			int j = e[i];
			in[j]--;// 处理与当前节点相关的邻接节点的入度
			s[j] = (s[j] + s[t]) % MOD;//更新到消费者的食物链数量 
			if(!in[j]) q[++tt] = j;// 如果入度为0，将其加入队列
		}
	}
}

int read()
{
    int t = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch <= '9' && ch >= '0') {
        t = t * 10 + ch - '0';
        ch = getchar();
    }
    return t * f;
} 

int main()
{
    n = read(),m = read();
    
    memset(h, -1, sizeof(h));//一定要初始化 
    
    while(m--)
    {
    	int u = read(),v = read();
    	add(u,v);
    	in[v]++;// 更新v的入度
    	out[u]++;//更新u的出度
	}
	
	topsort();
	
	int ans = 0;
	// 输出拓扑排序的节点数
    for(int i=1;i<=n;i++)//找出出度为0的点
        if(!out[i])
        	 ans = (ans + s[i])%MOD;
  
    cout<<ans;
    
    return 0;
}

查看全文

http://www.kler.cn/a/510013.html