缩点+DP
给定一个n个点m条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。
输入格式:
第一行,n,m
第二行,n个整数,依次代表点权
第三至m+2行,每行两个整数u,v,表示u->v有一条有向边
输出格式:
共一行,最大的点权之和。
输入样例#1:
2 2
1 1
1 2
2 1
输出样例#1:
2
n<=10^4,m<=10^5,|点权|<=1000 算法:Tarjan缩点+DAGdp
为什么要DP。。
跑完tarjan跑爆搜不就好了么。
还有这题貌似要开两个邻接表存。
不然会产生冲突(当然也有可能是我太弱了2333)
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<stack>
6 using namespace std;
7 const int MAXN=800100;
8 const int mod=998244353;
9 inline void read(int &n)
10 {
11 char c='+';bool flag=0;n=0;
12 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
13 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();
14 }
15 struct node
16 {
17 int u,v,nxt;
18 void cler()
19 {u=v=nxt=0;}
20 }edge[MAXN];
21 int head[MAXN];
22 int num=1;
23 inline void add_edge(int x,int y)
24 {
25 edge[num].u=x;
26 edge[num].v=y;
27 edge[num].nxt=head[x];
28 head[x]=num++;
29 }
30 struct node2
31 {
32 int u,v,nxt;
33 void cler()
34 {u=v=nxt=0;}
35 }edge2[MAXN];
36 int head2[MAXN];
37 int num2=1;
38 inline void add_edge2(int x,int y)
39 {
40 edge2[num2].u=x;
41 edge2[num2].v=y;
42 edge2[num2].nxt=head2[x];
43 head2[x]=num2++;
44 }
45 int n,m;
46 int dfn[MAXN];//时间顺序
47 int low[MAXN];
48 stack<int>s;
49 int tot=0;//总结点
50 int vis[MAXN];
51 int color[MAXN];
52 int colornum=0;
53 int date[MAXN];// 每一个联通分量里的权值
54 int a[MAXN];
55 int out;// 最终答案
56 int ans;// 当前答案
57 int dfs(int now)
58 {
59 if(vis[now]) return vis[now];
60 vis[now]=date[now];
61 int nowmax=0;
62 for(int i=head2[now];i!=-1;i=edge2[i].nxt)
63 {
64 if(!vis[edge2[i].v]) dfs(edge2[i].v);
65 nowmax=max(nowmax,vis[edge2[i].v]);
66 }
67 vis[now]+=nowmax;
68 return vis[now];
69 }
70 inline void tarjan(int now)
71 {
72 dfn[now]=low[now]=++tot;
73 vis[now]=1;
74 s.push(now);
75 for(int i=head[now];i!=-1;i=edge[i].nxt)
76 {
77 if(!dfn[edge[i].v]) tarjan(edge[i].v), low[now]=min(low[now],low[edge[i].v]);
78 else if(vis[edge[i].v]) low[now]=min(low[now],dfn[edge[i].v]);
79 }
80 if(dfn[now]==low[now])
81 {
82 colornum++;
83 int h;
84 do
85 {
86 h=s.top();
87 if(!color[s.top()]) color[s.top()]=colornum,date[colornum]+= a[s.top()];
88 vis[s.top()]=0; s.pop();
89 }while(now!=h);
90 }
91 }
92 int main()
93 {
94 read(n);read(m);
95 memset(head,-1,sizeof(head));
96 memset(head2,-1,sizeof(head2));
97 for(int i=1;i<=n;i++) read(a[i]);
98 for(int i=1;i<=m;i++)
99 {
100 int x,y;read(x);read(y);
101 add_edge(x,y);
102 }
103 for(int i=1;i<=n;i++)
104 if(!dfn[i]) tarjan(i);
105
106 for(int i=1;i<=n;i++)
107 for(int j=head[i];j!=-1;j=edge[j].nxt)
108 if(color[i]!=color[edge[j].v]) add_edge2(color[i],color[edge[j].v]);
109 memset(vis,0,sizeof(vis));
110 for(int i=1;i<=colornum;i++)
111 {
112 if(!vis[i])
113 dfs(i),ans=max(ans,vis[i]);
114 }
115 printf("%d",ans);
116 return 0;
117 }