P4017 最大食物链计数

本文主要是介绍P4017 最大食物链计数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: P4017 最大食物链计数

思路

这是一个关于食物链计数的问题。给定一个有向图，图中的每个节点表示一个生物，边表示食物链关系。每个节点的入度表示它的食物链数量。要求计算出所有节点的食物链数量之和。

解题方法

这个问题可以使用拓扑排序和动态规划的方法来解决。首先，我们需要构建一个有向图，使用链式前向星的方式存储图的边。然后，我们需要计算每个节点的入度。接下来，我们使用队列进行拓扑排序，将入度为0的节点入队，并初始化它们的食物链数量为1。然后，我们依次处理队列中的节点，更新它们的邻居节点的食物链数量，并将入度减1。如果邻居节点的入度变为0，我们将它入队。最后，我们将所有节点的食物链数量相加，得到最终的结果。

复杂度

时间复杂度:

这个算法的时间复杂度为$O(n+m)$，其中n是节点的数量，m是边的数量。

空间复杂度:

空间复杂度为$O(n)$。

Code

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static int MAXN = 5010;static int MAXM = 500010;static int MOD = 80112002;static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);// 链式前向星static int[] head = new int[MAXN];static int[] next = new int[MAXM];static int[] to = new int[MAXM];// 入度表static int[] indegree = new int[MAXN];// 食物链数量 传递的信息表static int[] lines = new int[MAXN];static int n, m, cnt, l, r;static int[] queue = new int[MAXN];static void build(int n) {cnt = 1;Arrays.fill(head, 0, n + 1, 0);Arrays.fill(lines, 0, n + 1, 0);Arrays.fill(indegree, 0, n + 1, 0);}static void addEdge(int f, int t) {next[cnt] = head[f];to[cnt] = t;head[f] = cnt++;}public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();build(n);for (int i = 0, from, to; i < m; i++) {from = nextInt();to = nextInt();addEdge(from, to);indegree[to]++;}out.println(ways());out.flush();}private static int ways() {l = r = 0;for (int i = 1; i <= n; i++) {if (indegree[i] == 0) {queue[r++] = i;lines[i] = 1;}}int ans = 0;while (l < r) {int u = queue[l++];if (head[u] == 0) {ans = (ans + lines[u]) % MOD;} else {for (int ei = head[u], v; ei > 0; ei = next[ei]) {v = to[ei];lines[v] = (lines[u] + lines[v]) % MOD;if (--indegree[v] == 0) {queue[r++] = v;}}}}return ans;}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}

这篇关于P4017 最大食物链计数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---