社区讨论

鸭了个蛋,求助

P4017最大食物链计数参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo224khc
此快照首次捕获于
2023/10/23 06:45
2 年前
此快照最后确认于
2023/11/03 07:07
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
/*
给定一个n节点,m边的有向无环图,
请你求出从入度为0的点~出度为0的点的所有连线。得数%80112002。
n<5000 m<500000
思路:拓扑排序+图上dp。
*/
int m,n;
struct dot{
    int r,c;
    vector <int> ljb;//邻接表
}dots[5003];
int dfs(int id);
int x,y;
long long answer;
int main(){
    cin>>n>>m;
    //吃-》被吃
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        dots[x].c++,dots[y].r++;
        dots[x].ljb.push_back(y);
    }
    answer=dfs(1);
    cout<<answer%80112002;
}
int dfs(int id){
    if(dots[id].c==0) return 1;
    else {
        int ans=0;
        for(int i=0;i<dots[id].c;i++) ans+=dfs(dots[id].ljb[i]);
        return ans;
    }
}

回复

1 条回复,欢迎继续交流。

正在加载回复...