洛谷 P4017 最大食物链计数 (拓扑排序,思维)

题意:有\(n\)个点,连\(m\)条边,求最多有多少条食物链(从头走到为有多少条路径).
题解:之前抽了点时间把拓扑排序补完了,这题其实就是一道拓扑排序的裸题.关于拓扑排序:

1.首先,我们用\(in\)记录某个点的入度,\(out\)表示这个点向外所连的点.

2.遍历所有点,找到入度为\(0\)的点,将其入队.

3.遍历队列(将队头元素记录并存入答案后弹出),将入度为\(0\)的点所连边一条一条的消去,即所有的\(out[x]=-1\),且该点所连的点的入度都需要\(-1\),如果某点的入度为\(0\),将其入队.

4.最后我们所得到的一定是某一种情况的拓扑序列.

那么对于该题,我们在求拓扑序列的同时,还要记录一下路径数,我们先使所有入度为\(0\)的点的路径数为\(1\),然后每次向外求拓扑序列时,对所有出边的点记录一个前缀和,最后累加一下出度为\(0\)的点的前缀和即可.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 80112002 ;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

int n,m;

int u,v;

int num[N];

vector<int> out[N];

vector<int> in(N,0);

vector<int> res;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

    cin>>n>>m;

    for(int i=0;i<m;++i){

        cin>>u>>v;

        in[v]++;

        out[u].pb(v);

    }

    queue<int> q;

    for(int i=1;i<=n;++i){

        if(in[i]==0){

            num[i]=1;

            q.push(i);

        }

    }

    while(!q.empty()){

        int now=q.front();

        q.pop();

        res.pb(now);

        for(auto w:out[now]){

            if(w!=-1){   //如果这条边存在

                in[w]--;

                num[w]=(num[w]+num[now])%mod;

                if(in[w]==0){

                    q.push(w);

                }

                w=-1;   //删去这条边,但好像没什么用?

            }

        }

    }

    int ans=0;

    for(int i=1;i<=n;++i){

        if(out[i].empty()){

            ans=(ans+num[i])%mod;

        }

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

洛谷 P4017 最大食物链计数 (拓扑排序,思维)

最新文章

热门文章