食物链 bzoj-4562 Haoi-2016
题目大意：给你n个点，m条边的DAG，求所有的满足条件的链，使得每条链的起点是一个入度为0的点，中点是一条出度为0的点。
注释：$1\le n\le 10^5$，$1\le m\le 2*10^5$。
想法：考试T2，全场切
动态规划
状态：dp[i]表示从这个点到出度为0的点的方案数。
转移：dp[i]+=dp[to[i]]
然后用记忆化爆搜即可。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define MOD 1000000007
#define N 100010
#define M 200010
using namespace std;
typedef long long ll;
ll dp[N];
int num[N];
char s[N][100];
map<string,int>mp;
// ll stack[M<<1];
// ll val(int a)
// {
// ll ans1=1,ans2=1,ans3=1;
// int k=strlen(s[a]+1);
// for(int i=1;i<=k/3;i++) ans1=ans1*(s[i]-'0')%mod;
// for(int i=k/3+1;i<=k/3*2;i++) ans2=ans2*(s[i]-'0')%mod;
// for(int i=k/3*2+1;i<=k;i++) ans3=ans3*(s[i]-'0')%mod;
// }
struct Node
{int val,id,now;
}qqq[N];
// int map[1000000];
int head[N],to[M],nxt[M],tot;
inline void add(int x,int y)
{to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}
int dfs(int pos,int fa)
{if(dp[pos]) return dp[pos];for(int i=head[pos];i;i=nxt[i]){if(to[i]==fa) continue;dp[pos]+=dfs(to[i],pos);dp[pos]%=MOD;}if(dp[pos]==0) dp[pos]=1;return dp[pos]%MOD;
}
inline bool cmp1(Node o,Node oo)
{return o.val<oo.val;
}
inline bool cmp2(Node o,Node oo)
{return o.id<oo.id;
}
ll sum[N];
int main()
{// freopen("chain.in","r",stdin);// freopen("chain.out","w",stdout);ll ans=0,/* top=0, */cnt=0;int m;scanf("%*d%d",&m);// puts("Fuck");for(int i=1;i<=m;i++){string s1,s2;cin >> s1 >> s2 ;if(!mp[s1]) mp[s1]=++cnt;if(!mp[s2]) mp[s2]=++cnt;add(mp[s1],mp[s2]);num[mp[s1]]++;sum[mp[s2]]++;// scanf("%s%s",s[1]+1,s[2]+1);// int x=val(1),y=val(2);// printf("Bitch %d %d\n",x,y);// top+=2;// stack[++top]=x,stack[++top]=y;// qqq[top-1].val=x,qqq[top].val=y;// qqq[top-1].id=top-1,qqq[top].id=top;// add(x,y);}// sort(qqq+1,qqq+top+1,cmp1);// qqq[0].val=qqq[1].val-1;// for(int i=1;i<=top;i++)// {// if(qqq[i-1].val!=qqq[i].val) cnt++;// qqq[i].now=cnt;// }// for(int i=1;i<=top;i++)// {// printf("Woc %d %d\n",qqq[i].val,qqq[i].now);// }// sort(qqq+1,qqq+top+1,cmp2);// for(int i=1;i<=top;i++)// {// printf("Fuck %d\n",qqq[i].now);// }// for(int i=2;i<=top;i+=2)// {// add(qqq[i-1].now,qqq[i].now);// sum[qqq[i].now]++;// maxnow=max(maxnow,sum[qqq[i].now]);// maxnow=max(maxno)// }for(int i=1;i<=cnt;i++){if(!sum[i]&&!num[i]) continue;if(!sum[i]) ans+=dfs(i,0);// printf("CaoNiMa %d\n",i);}// for(int i=1;i<=cnt;i++)// {// printf("EYWR %lld\n",dp[i]);// }printf("%lld\n",ans);return 0;
}
小结：先想到dp是关键。学长写的全是什么toposort..都是O(n)的...
