题解 P3183 【[HAOI2016]食物链】

_蒟蒻__ · 2019-11-06 19:22:55 · 题解

好多大佬用记搜， emm， 其实……

直接裸toposort加个f统计方案就好啦

考虑到拓扑排序的先后次序问题, 在更新入度的时候顺便将方案数进行累加

最后答案就是 \sum 无出边的点

注意单个点不算方案

生命苦短， 直接上代码

#include <iostream>
#include <vector>
#include <queue>
#define ORZ main
using namespace std;
const int N=1008611;
int n, m, f[N], rd[N];
vector <int> e[N];

inline int JI_DE_DIAN_GE_ZAN()
{
    queue <int> q;
    int ans=0;
    for(int i=1; i<=n; i++)
    if(!rd[i] && e[i].size()) // 单个点不算方案
        q.push(i), f[i]=1; 

    while(!q.empty())
    {
        int x=q.front(); q.pop();
        if(!e[x].size()) ans+=f[x];
        for(auto t : e[x])
        {
            f[t]+=f[x], rd[t]--; // f来统计方案
            if(!rd[t]) q.push(t);
        }
    }
    return ans;
} // 裸的

int ORZ ()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1, x, y; i<=m; i++)
    {
        cin>>x>>y; rd[y]++;
        e[x].push_back(y);
    }
    cout<<JI_DE_DIAN_GE_ZAN();
    return ~~ (0 ^ 0);
}