社区讨论
鸭了个蛋,求助
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 条回复,欢迎继续交流。
正在加载回复...