dp的思路是很简单的：设dp[i]为走到第i个点后能够得到的最大值
dp[i]=comfort[i]+Max{dp[j]|therer is edge(u,v)}
然而，一旦遇到一个环，这个算法会re+tle，因为无限地递归计算。
怎么办呢？

经典的做法：缩强联通分量。
把所有的强联通分量缩成一个点，comfort为个点的comfort之和，然后再用dp
这样，就不会遇到死循环的问题了。
这里，我为了方便，先把图用拓扑序排序一下，然后依次dp。

关键代码：
struct edge{
	int e;
	char type;
	edge *next;
}
struct Graph{
	int N;
	edge *E[NMax];
	int A[NMax];
}G1,G2;
void dfs1(int a){
	vi[a]=1;
	for (edge *p=G1.E[a];p;p=p->next)
		if (p->type && !vi[p->e])
			dfs1(p->e);
	rk[pt++]=a;
}
void dfs2(int a){
	belong[a]=pt;
	for (edge *p=G1.E[a];p;p=p->next)
		if (!p->type && belong[p->e]==-1)
			dfs2(p->e);
}
void dfs3(int a){
	vi[a]=1;
	for (edge *p=G2.E[a];p;p=p->next)
		if (!vi[p->e])
			dfs3(p->e);
	rk[pt++]=a;
}

//拓扑排序
                pt=0;
		for (int i=0;i<G1.N;i++)vi[i]=0;
		for (int i=0;i<G1.N;i++)if (!vi[i])
			dfs1(i);//记录出栈序
		pt=0;
		for (int i=0;i<G1.N;i++)belong[i]=-1;
		for (int i=G1.N-1;i>=0;i--)if (belong[rk[i]]==-1){
			dfs2(rk[i]);//缩合，染色
			pt++;
		}


//dp
                for (int i=0;i<G2.N;i++)vi[i]=0;
		pt=0;
		for (int i=0;i<G2.N;i++)if (!vi[i])
			dfs3(i);//拓扑排序
		int tmp;
		for (int i=0;i<G2.N;i++){
			x=rk[i];
			dp[x]=G2.A[x];tmp=0;
			for (edge *p=G2.E[x];p;p=p->next)
				tmp=(tmp<dp[p->e]?dp[p->e]:tmp);
			dp[x]+=tmp;
		}
                int ret;
		ret=0;
		for (int i=0;i<G2.N;i++)if (ret<dp[i])ret=dp[i];
		printf("%d\n",ret);

• 感激 (6) 5D6D 2012-04-22 11:36:11
• 这么大的N,DFS为什么不会爆？ (1563) 5D6D 2012-04-22 11:48:20