题意

求食物链,学过生物的都懂

不然,复习吧孩子,你无敌了

思路

本题使用邻接表

拓扑+小小改动

这个改动值继承上一个点的食物链总数

注意存储图的方向,谁被谁吃搞清楚

简图:

1 ← 2
↑ ↗↑
3 ← 5
↑ ↙
4

5 2 1
5 3 1
5 3 2 1
5 4 3 1
5 4 3 2 1

代码

#include<iostream>
#include<vector>
#include<queue>
#define N 114514
#define MOD 80112002
using namespace std;
int n,m,sum=0;
int ind[N];
int oud[N];
int cnt[N];
vector<int>g[N];
queue<int>q;
void topo()//拓扑排序
{
    for(int i=1;i<=n;i++)//找出食物链顶端的点
        if(!ind[i])
        {
            q.push(i);
            cnt[i]++;//这个点也算1条,自己也是1条食物链继承
        }
    while(!q.empty())//拓扑模板
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<(int)g[u].size();i++)
        {
            int v=g[u][i];
            cnt[v]+=cnt[u];//继承
            cnt[v]%=MOD;//取余
            if(--ind[v]==0)
            {
                q.push(v);
            }
        }
    }
}
int main()
{
    cin>>n>>m;//输入
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;//输入
        g[b].push_back(a);//注意存储图的方向,谁被谁吃搞清楚
        ind[a]++;//入度
        oud[b]++;//出度
    }
    topo();
    for(int i=1;i<=n;i++)
    {
        if(!oud[i])//找出食物链最底的生物
        {
            sum+=cnt[i];//求和
            sum%=MOD;//记得这里也要取余，不然40WA
        }
    }
    cout<<sum;//输出
    return 0;//完结散花
}

题意

从最小的生产者到最大的消费者的生物链的条数

思路

这道题和#P1144. 最短路计数的思路大体相同，只不过是用拓扑排序做。

首先将入度为 $0$ 的点入队，初始 $dis[i]$ 为 $1$（自己本身也是一条符合要求的生物链）

到一个点后将它相邻的点的 $dis$ 加上当前这个点的 $dis$。如果删掉 $u$ 与 $v$ 之间这条边后如果 $v$ 的入度为 $0$，那么就将 $v$ 入队。

最后将所有出度为 $0$ 的点的 $dis$ 加起来输出

思路解释（样例）

红→橙→黄→绿→蓝

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5005,M = 500005,MOD = 80112002;
vector<int> a[N];
int n,m,ind[N],outd[N],sum;
int dis[N];	// 第 i 个点为结尾的最大生物链的个数
void tp(){
	queue<int> q;
	for (int i = 1;i <= n;i++){
		if (!ind[i]){
			dis[i] = 1;	// 初始值为 1（自己也是 1 条生物链）
			q.push(i);
		}
	}
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for (int i = 0;i < a[x].size();i++){
			ind[a[x][i]]--;	// 删掉这条边
			dis[a[x][i]] += dis[x];	// 继承前一个结点的数量
			dis[a[x][i]] %= MOD;
			if (!ind[a[x][i]])	q.push(a[x][i]);
		}
	}
}
int main(int argc, char **argv){
	cin >> n >> m;
	for (int i = 0;i < m;i++){
		int u,v;
		cin >> u >> v;
		a[u].push_back(v);
		ind[v]++,outd[u]++;
	}
	tp();
	for (int i = 1;i <= n;i++){
		if (!outd[i])	sum += dis[i],sum %= MOD;
	}
	cout << sum;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
vector<int>g[500001]; 
queue<int>q;
int d[500001]; 
int c[500001];
int b[500001];
int main(){
	int n,m,s=0; 
	cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u1,v1;
    	cin>>u1>>v1;
    	c[v1]++;
    	d[u1]++;
    	g[v1].push_back(u1);
	}
	for(int i=1;i<=n;i++){
		if(d[i]==0){
			q.push(i);
			b[i]++;
		}
	}
	while(!q.empty()){
		int a=q.front();
	    q.pop();
	    int sz=g[a].size();
		for(int i=0;i<sz;i++){
		    b[g[a][i]]+=b[a];
		    b[g[a][i]]%=80112002;
			d[g[a][i]]--;
			if(d[g[a][i]]==0){	
			    q.push(g[a][i]);
		    } 	
		}
	}
	for(int i=1;i<=n;i++){
		if(c[i]==0){
			s+=b[i];
			s%=80112002;
		}
	}
	cout<<s;
}

#include <bits/stdc++.h> using namespace std; int n,m,ru[5005],chu[5005],a,b,f[5005],ans; int mp[5005][5005]; queue q; int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d", &a, &b); mp[a][b]=1; chu[a]++; ru[b]++; } for(int i=1;i<=n;i++){ if(ru[i]==0){ f[i]=1; q.push(i); } } while(!q.empty()){ int a=q.front(); q.pop(); for(int k=1;k<=n;k++){ if(mp[a][k]==0) continue; f[k]+=f[a]; f[k]%=80112002; ru[k]--; if(ru[k]==0){ if(chu[k]==0){ ans+=f[k]; ans%=80112002; continue; } q.push(k); } } } cout<<ans;

}

//邻接矩阵做的