Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

雁过留声——缩强连通分量+dp

Posted by fanhqme at 2009-12-13 17:16:04 on Problem 3160
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);

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator