题目内容

P4017

大意:给出 mn 种生物的捕食关系,求最大食物链(最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者)的条数。

保证给定的关系没有环

解题思路

一看,无环,想到 DAG,然后又看到最大食物链的定义:

最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者

就想到了最大食物链的左端必然是入度为 0 的点,右端必然是出度为 0 的点,因此使用拓扑排序。

我们设 f_i 为从入度为 0 的所有点到达点 i 的方案数总和,由于拓扑排序是在一个点的信息更新完之后再入队的,所以正确性得到了保证。

具体的做法就是普通的拓扑排序,记录每个点的入度,然后从入度为 0 的点开始,使用顺推,对于处理到的每一个点入度都减一,然后方案数加上去,特别的,如果从队列中取出的这个点的出度为 0,则统计答案。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=5e3+5,p=80112002;
vector<int> g[maxn];
int n,m,ind[maxn],f[maxn],ans;

inline int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        s=10*s+c-'0',c=getchar();
    return s;
}

void topo()
{
    queue<int> q;
    for(int i=1;i<=n;i++)//先扫一遍点,将入度为 0 的点加进去
        if(!ind[i])
            q.push(i),f[i]=1;//这里的初始状态很重要
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        if(g[now].size()==0)//如果出度为 0
        {
            ans=(ans+f[now])%p;//统计答案
            continue;
        }
        for(auto to:g[now])//遍历这个点的出边
        {
            f[to]=(f[to]+f[now])%p;//更新状态
            ind[to]--;//删边
            if(!ind[to])//如果这个点相连的信息都处理完了
                q.push(to);//入队
        }
    }
    return;
}

int main()
{
    n=read(),m=read();
    int a,b;
    for(int i=1;i<=m;i++)
    {
        a=read(),b=read();
        ind[a]++;//记录入度
        g[b].push_back(a);//加边
    }
    topo();//拓扑排序
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年3月13日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。