首页 > 代码库 > [HAOI2016]食物链
[HAOI2016]食物链
OJ题号：BZOJ4562、洛谷3183
思路：记忆化搜索。
本体可以转化成“求有向图中入度为0的结点到出度为0的结点的路径数”。
每次加边时记录每个结点的入度和出度，然后从入度为0的结点开始搜索，搜到出度为0的结点。
搜索到越底层，重复的路径越多，所以就要用记忆化的思想，将每个结点出发的路径个数记录下来，第二次搜到时直接调用。
1 #include<cstdio> 2 #include<vector> 3 const int N=100001; 4 std::vector<int> e[N]; 5 int in_degree[N]={0}; 6 void add_edge(const int a,const int b) { 7 e[a].push_back(b); 8 in_degree[b]++; 9 }10 bool isroot(const int x) {11 return !in_degree[x];12 }13 bool isleaf(const int x) {14 return !e[x].size();15 }16 int f[N]={0};17 int dfs(const int x) {18 if(f[x]) return f[x];19 if(isleaf(x)) return f[x]=1;20 int ans=0;21 for(int i=0;i<(int)e[x].size();i++) {22 ans+=dfs(e[x][i]);23 }24 return f[x]=ans;25 }26 int main() {27 int n,m;28 scanf("%d%d",&n,&m);29 for(int i=1;i<=m;i++) {30 int a,b;31 scanf("%d%d",&a,&b);32 add_edge(a,b);33 }34 int ans=0;35 for(int i=1;i<=n;i++) {36 if(isroot(i)&&!isleaf(i)) ans+=dfs(i);37 }38 printf("%d\n",ans);39 return 0;40 }
[HAOI2016]食物链
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。