博客

食物链 b

zoj-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)的…