poj 3160 Father Christmas flymouse 强连通+dp

本文主要是介绍poj 3160 Father Christmas flymouse 强连通+dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

       首先我们可以确定的是，对于val值小于0的节点都变成0.   假设一个集合内2个房间都能任意到达，那么我就可以吧集合内的所有点的价值都取到，并且可以达到任一点。实际上集合内的每个点是相同的，这样的集合就是一个强连通分量。 那么我们就可以用tarjin算法进行强连通缩点， 最后形成一个dag的图。在dag的图上面进行dp。可以先用拓扑排序后dp。或者建反响边记忆化搜索 。

VIEW  CDDE

//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<stdlib.h>
using namespace std;
const int mmax= 30010;
const int mod=1000000007;
typedef long long LL;struct node
{int st,en;int next;
}E[150010];
int p[mmax],fa[mmax];
int num;
void init()
{memset(p,-1,sizeof p);num=0;
}
void add(int st,int en)
{E[num].st=st;E[num].en=en;E[num].next=p[st];p[st]=num++;
}
int find(int x)
{if(x==fa[x])return x;return fa[x]=find(fa[x]);
}
int times,pp;
int low[mmax],dfn[mmax],Q[mmax];
bool instack[mmax];
void tarjin(int u)
{dfn[u]=low[u]=++times;Q[++pp]=u;instack[u]=1;for(int i=p[u];i+1;i=E[i].next){int v=E[i].en;if(!dfn[v]){tarjin(v);if(low[u]>low[v])low[u]=low[v];}else if(instack[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){while(pp){int x=Q[pp--];instack[x]=0;if(x==u)break;int xx=find(x);fa[xx]=u;}}
}LL dp[mmax],val[mmax];
LL sum[mmax];
int in[mmax];
bool vis[mmax];struct node2
{int st,en;int next;
}e[150010];
int p_[mmax];
int num_;
void init_()
{memset(p_,-1,sizeof p_);num_=0;
}
void add_(int st,int en)
{e[num_].st=st;e[num_].en=en;e[num_].next=p_[st];p_[st]=num_++;
}
queue<int>q;
int main()
{int n,m;//freopen("in.txt","r",stdin);while(cin>>n>>m){init();memset(dp,0,sizeof dp);memset(in,0,sizeof in);memset(sum,0,sizeof sum);for(int i=1;i<=n;i++)fa[i]=i;while(!q.empty())q.pop();for(int i=1;i<=n;i++)scanf("%lld",&val[i]);for(int i=0;i<m;i++){int u,v;scanf("%d %d",&u,&v);u++,v++;add(u,v);}times=pp=0;memset(instack,0,sizeof instack);memset(dfn,0,sizeof dfn);for(int i=1;i<=n;i++){if(!dfn[i])tarjin(i);}init_();memset(in,0,sizeof in);for(int i=1;i<=n;i++)sum[find(i)]+= val[i]>0? val[i]:0 ;for(int i=1;i<=n;i++){int u=find(i);for(int j=p[i];j+1;j=E[j].next){int v=find(E[j].en);if(u!=v)add_(u,v);}}memset(vis,0,sizeof vis);for(int i=1;i<=n;i++)if(i==find(i)) add_(0,i);q.push(0);vis[0]=1;while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=p_[x];i+1;i=e[i].next){int v=e[i].en;if(dp[v] < dp[x]+ sum[v]){dp[v]=dp[x]+sum[v];if(!vis[v]){q.push(v);vis[v]=1;}}}}LL ans=0;for(int i=1;i<=n;i++)ans=ans<dp[i]?dp[i]:ans;cout<<ans<<endl;}return 0;
}

这篇关于poj 3160 Father Christmas flymouse 强连通+dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---