poj3160 强连通+记忆化搜索

题意:有一张 n 点 m 边的有向无环图,每个点有各自的权值,可正可负,现在从一个点开始走,一直走到不能走到其他点为止,每经过一个点,可以选择获得或不获得它的权值,每个点可以走多次,但是权值只能获得一次,问最后最多能够获得多少权值。

每个点可以走多次,权值只能获得一次,路过的时候权值可以不获得,所以我们只需要考虑正的权值就行了。在一个强连通分量中的点的权值我们都能获得,所以先缩点,得到一个有向无环图,然后从每个入度为 0 的点开始DFS,累计得到的最大权值就行。

 #include<stdio.h>
#include<string.h>
#include<stack>
#include<queue>
using namespace std; const int maxn=3e4+;
const int maxm=2e5+; int head[][maxn],point[][maxm],nxt[][maxm],size[];
int n,t,scccnt;
int stx[maxn],low[maxn],scc[maxn],num[maxn],id[maxn],v[maxn];
int dp[maxn];
stack<int>S; int max(int a,int b){return a>b?a:b;} void init(){
memset(head,-,sizeof(head));
size[]=size[]=;
memset(num,,sizeof(num));
memset(id,,sizeof(id));
memset(dp,-,sizeof(dp));
} void add(int a,int b,int c=){
point[c][size[c]]=b;
nxt[c][size[c]]=head[c][a];
head[c][a]=size[c]++;
} void dfs(int s){
stx[s]=low[s]=++t;
S.push(s);
for(int i=head[][s];~i;i=nxt[][i]){
int j=point[][i];
if(!stx[j]){
dfs(j);
low[s]=min(low[s],low[j]);
}
else if(!scc[j]){
low[s]=min(low[s],stx[j]);
}
}
if(low[s]==stx[s]){
scccnt++;
while(){
int u=S.top();S.pop();
scc[u]=scccnt;
num[scccnt]+=v[u]>?v[u]:;
if(s==u)break;
}
}
} void setscc(){
memset(stx,,sizeof(stx));
memset(scc,,sizeof(scc));
t=scccnt=;
for(int i=;i<=n;++i)if(!stx[i])dfs(i);
for(int i=;i<=n;++i){
for(int j=head[][i];~j;j=nxt[][j]){
int k=point[][j];
if(scc[i]!=scc[k]){
add(scc[i],scc[k],);
id[scc[k]]++;
}
}
}
} int dfs1(int s){
if(~dp[s])return dp[s];
int maxx=;
for(int i=head[][s];~i;i=nxt[][i]){
int j=point[][i];
maxx=max(maxx,dfs1(j));
}
dp[s]=maxx+num[s];
return dp[s];
} int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
init();
for(int i=;i<=n;++i)scanf("%d",&v[i]);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
a++;
b++;
add(a,b);
}
setscc();
int ans=;
for(int i=;i<=scccnt;++i){
if(!id[i])ans=max(ans,dfs1(i));
}
printf("%d\n",ans);
}
return ;
}
上一篇:Domain logic approaches


下一篇:sqlserver中的循环遍历(普通循环和游标循环)