P4017 最大食物链计数
记忆化搜索 DP
角度解
- 从捕食者向被捕食者建边
- 维护每个生物的捕食
eat
,和被捕食数量beat
。 - 对每一个食物链顶端
dfs
,向下搜索直到找到最低级的生物,记忆化当前结点对应的食物链长度。
#include <iostream>
#include <algorithm>
#include <cstring>
#define mod %80112002
using namespace std;
const int N = 5e3 + 5;
const int M = 5e5 + 5;
struct Node{
int to, next;
}edge[M];
int head[N];
int cnt = 0;
int n, m;
int ans;
int eat[N], beat[N], F[N];
void addEdge(int a, int b)
{
edge[cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt++;
}
void preProcessing()
{
memset(head, -1 , sizeof(head));
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
addEdge(b, a);
eat[b]++;
beat[a]++;
}
}
int dfs(int u)
{
int sum = 0;
if (!eat[u])
{
return 1;
}
if (F[u])
{
return F[u];
}
for (int j = head[u]; j != -1; j = edge[j].next)
{
sum = (sum + dfs(edge[j].to)) mod;
}
return F[u] = sum;
}
int main()
{
preProcessing();
for (int i = 1; i <= n; i++)
{
if (!beat[i])
{
ans += dfs(i);
ans = ans mod;
}
}
cout << ans;
return 0;
}
拓扑排序角度解
- 从被捕食者向捕食者建边
- 维护每个生物(结点)的入度
ind
,和出度otd
。 - 直接对整个食物网拓扑排序,排序的过程中自然维护一个
num
数组表示到当前结点的最长链。 - 求和出度为 \(0\) 的
num
数组即可。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define mod %80112002
using namespace std;
const int N = 5e3 + 5;
const int M = 5e5 + 5;
struct Node{
int to, next;
}edge[M];
int head[N];
int cnt = 0;
int n, m;
int ans;
int ind[N], otd[N], F[N], num[N];
void addEdge(int a, int b)
{
edge[cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt++;
}
void preProcessing()
{
memset(head, -1 , sizeof(head));
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
addEdge(a, b);
ind[b]++;
otd[a]++;
}
}
void bfs()
{
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (!ind[i]) num[i] = 1, q.push(i);
}
while(!q.empty())
{
int f = q.front();
q.pop();
for (int i = head[f]; i != -1; i = edge[i].next)
{
int t = edge[i].to;
--ind[t];
num[t] = (num[t] + num[f]) mod;
if (ind[t] == 0) q.push(t);
}
}
}
int main()
{
preProcessing();
bfs();
for (int i = 1; i <= n; i++)
{
if (!otd[i])
{
ans = (ans + num[i]) mod;
ans = ans mod;
}
}
cout << ans;
return 0;
}
标签:食物链,head,int,++,cnt,计数,edge,include,P4017
From: https://www.cnblogs.com/kdlyh/p/17864768.html