和上一道题一样，可以用DAG上的动态规划来做，也可以建立一个源点，用spfa来做
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<stack>
6 #include<vector>
7 using namespace std;
8
9 const int maxn = 5005;
10 int n,m;
11 int first[maxn];
12 int sc[maxn],scn[maxn],low[maxn],pre[maxn];
13 int scnt,ecnt,dfs_clock;
14 int dp[maxn];
15
16 int first1[maxn];
17 int ecnt1;
18
19 int a[maxn];
20 int in[maxn];
21
22 struct Edge{
23 int v,next;
24 }e[maxn*10];
25
26 Edge e1[maxn*10];
27
28 stack<int> S;
29
30 void init(){
31 ecnt = ecnt1 = 0;
32 memset(first,-1,sizeof(first));
33 memset(first1,-1,sizeof(first1));
34 memset(dp,0,sizeof(dp));
35 }
36
37 void addedges(int u,int v){
38 e[ecnt].v = v;
39 e[ecnt].next = first[u];
40 first[u] = ecnt++;
41 }
42
43 void addedges1(int u,int v){
44 e1[ecnt1].v = v;
45 e1[ecnt1].next = first1[u];
46 first1[u] = ecnt1++;
47 }
48
49 void dfs(int u){
50 low[u] = pre[u] = ++dfs_clock;
51 S.push(u);
52 for(int i = first[u];~i;i = e[i].next){
53 int v = e[i].v;
54 if(!pre[v]){
55 dfs(v);
56 low[u] = min(low[u],low[v]);
57 }
58 else if(!sc[v]) low[u] = min(low[u],pre[v]);
59 }
60 if(pre[u] == low[u]){
61 scnt++;
62 for(;;){
63 int x = S.top();S.pop();
64 sc[x] = scnt;
65 scn[scnt]+= a[x];
66 if(x == u) break;
67 }
68 }
69 }
70
71 void find_scc(){
72 while(!S.empty()) S.pop();
73 scnt = dfs_clock = 0;
74 memset(low,0,sizeof(low));memset(pre,0,sizeof(pre));
75 memset(sc,0,sizeof(sc));memset(scn,0,sizeof(scn));
76
77 for(int i = 1;i <= n;i++) if(!pre[i]) dfs(i);
78 }
79
80 int solve(int p){
81 if(dp[p]) return dp[p];
82 for(int i = first1[p];~i;i = e1[i].next){
83 int v = e1[i].v;
84 dp[p] = max(dp[p],solve(v));
85 }
86 return dp[p] = dp[p] + scn[p];
87 }
88
89 int main(){
90 int T;
91 while(scanf("%d %d",&n,&m) != EOF){
92 init();
93 for(int i = 1;i <= n;i++) {
94 scanf("%d",&a[i]);
95 if(a[i] < 0) a[i] = 0;
96 }
97 for(int i = 0;i < m;i++ ){
98 int u,v;
99 scanf("%d %d",&u,&v);u++;v++;
100 addedges(u,v);
101 }
102 find_scc();
103
104 memset(in,0,sizeof(in));
105 for(int u = 1;u <= n;u++){
106 for(int i = first[u];~i;i = e[i].next){
107 int v = e[i].v;
108 if(sc[u] != sc[v]) addedges1(sc[u],sc[v]),in[sc[v]]++;
109 }
110 }
111
112 int ans = 0;
113 for(int i = 1;i <= scnt;i++) {
114 ans = max(ans,solve(i));
115 }
116 printf("%d\n",ans);
117 }
118 return 0;
119 } View Code
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<stack>
6 #include<vector>
7 #include<queue>
8 using namespace std;
9
10 const int maxn = 5005;
11 const int INF = 1000000005;
12 int n,m;
13 int first[maxn];
14 int sc[maxn],scn[maxn],low[maxn],pre[maxn];
15 int scnt,ecnt,dfs_clock;
16 int dp[maxn];
17
18 int du[maxn];
19 int dis[maxn];
20 int inq[maxn];
21
22 int first1[maxn];
23 int ecnt1;
24
25 struct Edge{
26 int v,next;
27 }e[maxn*10];
28
29 Edge e1[maxn*10];
30
31 stack<int> S;
32 vector<int> g[maxn];
33 int val[maxn],a[maxn];
34
35 void init(){
36 ecnt = ecnt1 = 0;
37 memset(first,-1,sizeof(first));
38 memset(val,0,sizeof(val));
39 memset(du,0,sizeof(du));
40 }
41
42 void addedges(int u,int v){
43 e[ecnt].v = v;
44 e[ecnt].next = first[u];
45 first[u] = ecnt++;
46 }
47
48 void dfs(int u){
49 low[u] = pre[u] = ++dfs_clock;
50 S.push(u);
51 for(int i = first[u];~i;i = e[i].next){
52 int v = e[i].v;
53 if(!pre[v]){
54 dfs(v);
55 low[u] = min(low[u],low[v]);
56 }
57 else if(!sc[v]) low[u] = min(low[u],pre[v]);
58 }
59 if(pre[u] == low[u]){
60 scnt++;
61 for(;;){
62 int x = S.top();S.pop();
63 sc[x] = scnt;
64 val[scnt] += a[x];
65 if(x == u) break;
66 }
67 }
68 }
69
70 void find_scc(){
71 while(!S.empty()) S.pop();
72 scnt = dfs_clock = 0;
73 memset(low,0,sizeof(low));memset(pre,0,sizeof(pre));
74 memset(sc,0,sizeof(sc));memset(scn,0,sizeof(scn));
75
76 for(int i = 1;i <= n;i++) if(!pre[i]) dfs(i);
77 }
78
79
80 int spfa(){
81 memset(inq, 0, sizeof(inq));
82 queue<int>q;
83 g[0].clear();
84 q.push(0);
85 dis[0] = 0; val[0] = 0;
86 for(int i = 1; i <= scnt; i++){if(du[i] == 0)g[0].push_back(i); dis[i] = -INF;}
87 int ans = 0;
88 while(!q.empty()){
89 int u = q.front(); q.pop(); inq[u] = 0;
90 for(int i = 0; i < g[u].size(); i++){
91 int v = g[u][i];
92 if(dis[v] < dis[u] + val[v]){
93 dis[v] = dis[u] + val[v];
94 ans = max(ans, dis[v]);
95 if(inq[v] == 0)inq[v] = 1, q.push(v);
96 }
97 }
98 }
99 return ans;
100 }
101
102 int main(){
103 while(scanf("%d %d",&n,&m) != EOF){
104 init();
105 for(int i = 1;i <= n;i++) {
106 scanf("%d",&a[i]);
107 if(a[i] < 0) a[i] = 0;
108 }
109 for(int i = 0;i < m;i++ ){
110 int u,v;
111 scanf("%d %d",&u,&v);u++;v++;
112 addedges(u,v);
113 }
114 find_scc();
115 for(int i = 1;i <= scnt;i++) g[i].clear();
116
117 for(int u = 1;u <= n;u++){
118 for(int i = first[u];~i;i = e[i].next){
119 int v = e[i].v;
120 if(sc[u] != sc[v]) g[sc[u]].push_back(sc[v]),du[sc[v]]++;
121 }
122 }
123 printf("%d\n",spfa());
124 }
125 return 0;
126 } View Code
转载于:https://www.cnblogs.com/wuyuewoniu/p/4700260.html