【bzoj4562】HAOI2016食物链

记忆化搜索水过去了……

QwQ

#include<bits/stdc++.h>
#define N 400010
typedef long long ll;
using namespace std;
int head[*N],tot=,in[N],out[N],n,m;
struct Edge{int u,v,next;}G[N<<];
inline void addedge(int u,int v){
G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot;
}
ll dp[N];
ll dfs(int u){
if(dp[u])return dp[u];ll ans=;
if(!out[u]&&in[u])++ans;
for(int i=head[u];i;i=G[i].next){
int v=G[i].v;ans+=dfs(v);
}
dp[u]=ans;return ans;
}
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();m=read();
for(int i=,u,v;i<=m;i++){
u=read();v=read();out[u]++;in[v]++;
addedge(u,v);
}
ll ans=;
for(int i=;i<=n;i++)if(!in[i])ans+=dfs(i);
cout<<ans<<endl;
}
上一篇:【bzoj4562】[Haoi2016]食物链 拓扑排序+dp


下一篇:手把手实现微信网页授权和微信支付,附源代码(VUE and thinkPHP)