题目
题目来源：CCF HAOI2016；
题目描述
如图所示为某生态系统的食物网示意图，据图回答第 (1) 小题。
现在给你 (n) 个物种和 (m) 条能量流动关系，求其中的食物链条数。物种的名称为从 (1) 到 (n) 编号。
(m) 条能量流动关系形如：
[a_1quad b_1
]
[a_2quad b_2
]
[a_3quad b_3
]
[cdots
]
[a_{m-1}quad b_{m-1}
]
[a_mquad b_m
]
其中 (a_i)、(b_i) 表示能量从物种 (a_i) 流向物种 (b_i)，注意单独的一种孤立生物不算一条食物链。
输入格式
第一行两个整数 (n) 和 (m)；
接下来 (m) 行每行两个整数 (a_i)、(b_i) 描述 (m) 条能量流动关系。
输出格式
一个整数即食物网中的食物链条数。
数据规模及约定
(1le nle 10^5)，(0le mle 2 imes 10^5)。
保证输入数据符合生物学特点，且不会有重复的能量流动关系出现。题目保证答案不会爆 int。
分析
题意是给你一张 DAG，求出满足起点入度为 (0)，终点出度为 (0) 的路径的数量。
这显然是一个很简单的搜索，最简单的方法就是从每一个入度为 (0) 的点进行 DFS 并统计。但是这并不一定可以通过。
注意到这是一个 DAG，所以我们进行记忆化。记录 (f_i) 为第 (i) 个点作为起点，终点出度为 (0) 的路径数量。
那么，对于一个节点，(f_i) 的值就是所有其后继节点的 (f_j) 的和，如果有一个后继节点没有后继节点，那么就对原节点 (+1)，创建一条新的路径。
相比来说，这个算法的优点在于每一个节点只处理一次，复杂度是 (O(n+m))，绰绰有余。
Code
一定要记住，一个节点并不能算作一条路径，在代码中要体现这一点。
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
const int max_n = 100000, max_m = 200000; // 常量
int hd[max_n], des[max_m], nxt[max_m], ind[max_n] = {}, e_cnt = 0; // 邻接表存图和入度统计
bool vis[max_n] = {}; // 是否处理过
long long dp[max_n] = {}, ans = 0; // 记忆化
inline int read() // 快读
{
int ch = getchar(), t = 1, n = 0;
while (isspace(ch)) { ch = getchar(); }
if (ch == '-') { t = -1, ch = getchar(); }
while (isdigit(ch)) { n = n * 10 + ch - '0', ch = getchar(); }
return n * t;
}
void add_edge(int s, int t)
{
des[e_cnt] = t;
nxt[e_cnt] = hd[s];
hd[s] = e_cnt++;
}
void dfs(int id) // 搜索
{
vis[id] = true; // 标记
if (hd[id] == -1) // 出度为0
{
dp[id] = -666; // 标记
return;
}
for (int p = hd[id]; p != -1; p = nxt[p]) // 遍历后继节点
{
if (!vis[des[p]]) // 处理
dfs(des[p]);
if (dp[des[p]] == -666) // 有标记
dp[id]++; // 新建一条路径
else
dp[id] += dp[des[p]]; // 否则累加
}
}
int main()
{
memset(hd, -1, sizeof(hd)); // 初始化
int n = read(), m = read(), ta, tb;
for (int i = 0; i < m; i++) // 输入
{
ta = read(), tb = read();
add_edge(ta - 1, tb - 1); // 建图
ind[tb-1]++; // 统计入度
}
for (int i = 0; i < n; i++)
if (!ind[i]) // 入度为0
{
dfs(i); // 计算
if (dp[i] != -666) // 不是单独节点
ans += dp[i]; // 统计
}
printf("%lld
", ans); // 精准结束
return 0;
}
后记
这道题的一个重点就是一个点不能作为一条路径，这一点当时卡了 5ab 好久，后来在看题解时才恍然大悟。
做题时，注意题目中的关键是很重要的，这可能就是拉分的关键。