【bzoj4562】[Haoi2016]食物链 拓扑排序+dp

原文地址:http://www.cnblogs.com/GXZlegend/p/6832118.html


题目描述

如图所示为某生态系统的食物网示意图,据图回答第1小题
现在给你n个物种和m条能量流动关系,求其中的食物链条数。
物种的名称为从1到n编号
M条能量流动关系形如
a1 b1
a2 b2
a3 b3
......
am-1 bm-1
am bm
其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链

输入

第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。
(数据保证输入数据符号生物学特点,且不会有重复的能量流动关系出现)
1<=N<=100000 0<=m<=200000
题目保证答案不会爆 int

输出

一个整数即食物网中的食物链条数

样例输入

10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9

样例输出

9


题目大意

给定你一个DAG图,求任意一条从入度为0的点到出度为0的点的方案数,其中不包括入度和出度都为0的点

题解

拓扑排序+dp,难在题意

设f[i]表示从某个入度为0的点到点i的方案数,然后按照类似拓扑排序的方法,由入度为0的点更新其它点。

注意一下入度和出度都为0的点要特判一下。

#include <cstdio>
#include <cstring>
#include <queue>
#define N 100010
using namespace std;
queue<int> q;
int head[N] , to[N << 1] , next[N << 1] , cnt , rd[N] , cd[N] , f[N];
void add(int x , int y)
{
to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;
}
int main()
{
int n , m , i , x , y , ans = 0;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , cd[x] ++ , rd[y] ++ ;
for(i = 1 ; i <= n ; i ++ )
{
if(!rd[i])
{
if(cd[i]) f[i] = 1;
q.push(i);
}
}
while(!q.empty())
{
x = q.front() , q.pop();
for(i = head[x] ; i ; i = next[i])
{
f[to[i]] += f[x] , rd[to[i]] -- ;
if(!rd[to[i]]) q.push(to[i]);
}
}
for(i = 1 ; i <= n ; i ++ ) if(!cd[i]) ans += f[i];
printf("%d\n" , ans);
return 0;
}
上一篇:《嵌入式Linux基础教程学习笔记一》


下一篇:【bzoj4562】HAOI2016食物链