给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
有环我们很不好判断，但是显然在一个强连通分量里面的点我们都可以到达。
所以缩起来之后就是一个DAG，之后随便你怎么算都行（bfs/dfs）
（我觉得并不算是dp emmm）
#include#include #include #include #include #include using namespace std;typedef long long ll;const int N=1e4+5;const int M=1e5+5;inline int read(){ int x=0,w=1;char ch=0; while(ch<'0'||ch>'9'){ if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*w;}struct node{ int w,to,nxt;}e[2][M];int cnt,h[2][N];inline void add(int u,int v,int k){ e[k][++cnt].to=v;e[k][cnt].nxt=h[k][u];h[k][u]=cnt;}int dfn[N],low[N],val[N],to[N],sum[N],f[N],indeg[N],t,l;stack q;queue p;bool inq[N],vis[N];void tarjan(int u){ int v; dfn[u]=low[u]=++t; q.push(u);inq[u]=1; for(int i=h[0][u];i;i=e[0][i].nxt){ v=e[0][i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(inq[v]){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ l++; do{ v=q.top(); q.pop(); inq[v]=0; to[v]=l; sum[l]+=val[v]; }while(v!=u); }}void bfs(int u){ vis[u]=1;f[u]=sum[u]; p.push(u); while(!p.empty()){ u=p.front();p.pop();vis[u]=0; for(int i=h[1][u];i;i=e[1][i].nxt){ int v=e[1][i].to; if(f[v]
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：
+++++++++++++++++++++++++++++++++++++++++++