BZOJ1050 [HAOI2006]旅行comf

题面

​ 给定一个DAG,求入度为0的点到出度为0的点的路劲有多少条——不包括出度和入度都为0的

题解

​ 直接记忆化DP。

​ 代码很短呀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<vector>
using namespace std;
typedef long long LL;
#define N 100005
vector<int> edge[N];
int In[N],Out[N],f[N],n,m;
int dfs(int u){
if (f[u]!=-1) return f[u];
f[u] = 0;
for (int j=0;j<edge[u].size();j++){
int v = edge[u][j];
f[u] += dfs(v);
}
return f[u];
}
int Ans = 0;
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
edge[a].push_back(b);
In[b]++;
Out[a]++;
}
memset(f,-1,sizeof(f));
for (int i=1;i<=n;i++)
if (Out[i]==0 && In[i]!=0) f[i]=1; else
if (Out[i]==0 && In[i]==0) f[i]=0;
for (int i=1;i<=n;i++){
if (In[i] == 0) Ans += dfs(i);
}
printf("%d\n",Ans);
return 0;
}
文章目录
  1. 1. 题面
  2. 2. 题解