给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
因为可以重复经过点，所以一个点所在的强联通分量必定可以到达。所以直接缩点即可。
缩点之后，我们要让权值最大化，必须从入度为0的点开始搜。因为这是DAG，入度不为零的点的最后祖先必定是入度为零的点。由于这道题没有负数权值，从入度为零的结点开始走肯定是一个最好的选择。然后DAG上跑动归即可。
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 5 const int maxn=1e4+5, maxm=1e5+5; 6 7 class Graph{ 8 public: 9 //为什么用嵌套类，因为声明很烦。。并不是访问问题的原因。 10 //如果类的成员不是static的话，内部类是不知道获取哪个外部类对象的。。 11 //所以无论是把类放在里面还是外面，访问都有问题。 12 //另外，把private放在下面，应该是因为嵌套类类必须完全声明才能使用吧。。 13 //我也不大清楚。。先这么用着，以后再去翻c++ primer。 14 class Edge{ 15 private: 16 Graph *belong; 17 public: 18 int v, to, next; //感觉这里还是不优雅。。 19 Edge(){} 20 Edge(Graph& g, int x, int y, int z){ 21 belong=&g; 22 to=x, v=y, next=z; 23 } 24 Edge operator ++(){ //不能打引用！ 25 *this=belong->edge[next]; //因为有自增运算，这个edge不能等同于图中的！ 26 return *this; 27 } 28 int operator *(){ 29 return to; 30 } 31 }; 32 Graph(){} 33 void addedge(int x, int y, int v){ 34 ++cntedge; 35 edge[cntedge]=Edge(*this, y, v, fir[x]); 36 fir[x]=cntedge; 37 return; 38 } 39 Edge get_link(int x){ //这里改成begin较好 40 return edge[fir[x]]; 41 } 42 private: 43 int cntedge, fir[maxn]; 44 Edge edge[maxm]; 45 }; 46 47 int n, m, cnttime, cntscc; 48 int v[maxn], visit[maxn], time[maxn]; 49 int scc[maxn], vofscc[maxn], in[maxn], ans[maxn]; 50 Graph g, g_t, g_scc; 51 52 void dfs(int now, int flag){ 53 visit[now]=1; 54 Graph::Edge e=g.get_link(now); 55 if (flag==2) e=g_t.get_link(now); 56 int to=*e; 57 while (to){ 58 if (!visit[to]) dfs(to, flag); 59 to=*(++e); 60 } 61 if (flag==1){ 62 ++cnttime; 63 time[cnttime]=now; 64 } 65 if (flag==2) { 66 scc[now]=cntscc; 67 vofscc[cntscc]+=v[now]; 68 } 69 return; 70 } 71 72 void dfs2(int x){ 73 Graph::Edge e=g.get_link(x); 74 int to=*e; 75 visit[x]=1; 76 while (to){ 77 if (scc[to]!=scc[x]){ 78 g_scc.addedge(scc[x], scc[to], v[scc[to]]); 79 ++in[scc[to]]; 80 } 81 if (!visit[to]) 82 dfs2(to); 83 to=*(++e); 84 } 85 return; 86 } 87 88 void dfs3(int x){ 89 Graph::Edge e=g_scc.get_link(x); 90 int to=*e; 91 visit[x]=1; 92 ans[x]=vofscc[x]; 93 while (to){ 94 if (!visit[to]) dfs3(to); 95 if (ans[to]+vofscc[x]>ans[x]) 96 ans[x]=ans[to]+vofscc[x]; 97 to=*(++e); 98 } 99 return; 100 } 101 102 int main(){ 103 scanf("%d%d", &n, &m); 104 for (int i=1; i<=n; ++i) 105 scanf("%d", &v[i]); 106 int x, y; 107 for (int i=1; i<=m; ++i){ 108 scanf("%d%d", &x, &y); 109 g.addedge(x, y, 1); 110 g_t.addedge(y, x, 1); 111 } //建图 112 for (int i=1; i<=n; ++i) 113 if (!visit[i]) dfs(i, 1); //时间戳 114 memset(visit, 0, sizeof(visit)); 115 for (int i=n; i>0; --i){ 116 if (!visit[time[i]]){ 117 ++cntscc; 118 dfs(time[i], 2); 119 } 120 } //求强联通分量 121 memset(visit, 0, sizeof(visit)); 122 for (int i=1; i<=n; ++i){ 123 if (!visit[i]) dfs2(i); 124 } //缩点 125 for (int i=1; i<=cntscc; ++i) 126 if (!in[i]) g_scc.addedge(0, i, vofscc[i]); //超级源汇 127 memset(visit, 0, sizeof(visit)); 128 dfs3(0); //树形dp 129 printf("%d ", ans[0]); 130 return 0; 131 }