首先，从模板题开始学起——
思路：
1. 这道题为什么要 缩点？（什么时候需要缩点）
根据题目意思，我们只需要找出一条点权最大的路径就行了，不限制点的个数。那么考虑对于一个环上的点被选择了，一整条环是不是应该都被选择，这一定很优，能选干嘛不选。很关键的是题目还允许我们重复经过某条边或者某个点，我们就不需要考虑其他了。因此整个环实际上可以看成一个点（选了其中一个点就应该选其他的点）
——摘录自洛谷第一篇题解
2. 将强连通分量缩点 -> 建边成为DAG -> DPmax
1 #include<cstdio>
2 #include<queue>
3 #include<vector>
4 #include<cstring>
5 #include<algorithm>
6 #define N 100010
7 #define M 500010
8 using namespace std;
9
10 struct node{
11 int from,to,next;
12 }edge[M];
13 queue < int > q;
14 vector < int > cd[N]; //出度
15 vector < int > rd[N]; //入度
16 int ans[M],t,x,y,v,rds[N],u,n,m,sum,vis[N],d[N],dis[N];
17 int dfn[N],low[N],f[N],time,cnt,k;
18 int stack[N],head[M],visit[N],tot,id;
19
20 void add(int x,int y){ //邻接表加边
21 edge[++cnt].next=head[x];
22 edge[cnt].from=x;
23 edge[cnt].to=y;
24 head[x]=cnt;
25 }
26
27 void tarjan(int x){
28 dfn[x]=low[x]=++time; //更新时间
29 stack[++id]=x; //手写栈
30 visit[x]=1; //入栈
31 for(int i=head[x];i;i=edge[i].next){
32 if(!dfn[edge[i].to]){ //没有更新到的点
33 tarjan(edge[i].to);
34 low[x]=min(low[x],low[edge[i].to]);
35 }
36 else{
37 if(visit[edge[i].to]) //更新过的点
38 low[x]=min(low[x],dfn[edge[i].to]);
39 }
40 }
41 if(low[x]==dfn[x]){ //注意不在 for 循环内
42 tot++; //强连通分量编号 (缩点的编号)
43 while(1){
44 vis[stack[id]]=tot; //vis记录缩点的编号
45 dis[tot]+=d[stack[id]]; //缩点的权值=强连通分量权值累加
46 visit[stack[id]]=0,id--; //出栈
47 if(x==stack[id+1]) break; //这个连通块已弹完
48 }
49 }
50 }
51 void topo(){ //拓扑排序
52 for(int i=1;i<=tot;i++) if(rds[i]==0) q.push(i); //入度数(rds)为 0 ,进队
53 while(!q.empty()){
54 int u=q.front();
55 q.pop(); //队头出队
56 ans[++k]=u; //ans记录按拓扑序排列的点
57 for(int i=1;i<=cd[u].size();i++){ //cd[u].size(): cd[u][]的长度
58 v=cd[u][i-1]; //因为 vector是从 0开始的,所以减 1
59 rds[v]--; //入度数--
60 if(rds[v]==0) q.push(v); //入度数(rds)为 0 ,进队
61 }
62 }
63 }
64
65 int main()
66 {
67 scanf("%d%d",&n,&m);
68 for(int i=1;i<=n;i++) scanf("%d",&d[i]);
69 for(int i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y);
70
71 for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); // tarjan缩点
72
73 for(int i=1;i<=cnt;i++){ //把缩好的点 建边 ->DAG
74 if(vis[edge[i].from]!=vis[edge[i].to]){
75 x=vis[edge[i].from],y=vis[edge[i].to]; // 建 x->y 的边
76 rds[y]++; // y 的入度数++
77 rd[y].push_back(x); // 把 x 放入 y 的入度
78 cd[x].push_back(y); // 把 y 放入 x 的出度
79 }
80 }
81 topo(); // DAG上跑拓扑
82 for(int i=1;i<=tot;i++){ //按照拓扑序(无后效性) 跑 DP
83 int w=ans[i];
84 f[w]=dis[w];
85 for(int j=1;j<=rd[w].size();j++)
86 f[w]=max(f[w],f[rd[w][j-1]]+dis[w]); //因为 vector是从 0开始的,所以减 1
87 }
88
89 for(int i=1;i<=tot;i++) sum=max(f[i],sum); //最后统计答案
90 printf("%d",sum);
91 return 0;
92 }
View Code
1 #include<cstdio>
2 #include<algorithm>
3 #define N 100010
4 using namespace std;
5 struct node{
6 int next,to;
7 }edge[N*2];
8 int n,m,dfn[N],cut[N],head[N],low[N],tot,cnt,id;
9
10 void add(int x,int y){
11 edge[++cnt].next=head[x];
12 edge[cnt].to=y;
13 head[x]=cnt;
14 }
15
16 void tarjan(int x,int root){ //割点
17 int child=0;
18 dfn[x]=low[x]=++id;
19 for(int v,i=head[x];i;i=edge[i].next){
20 v=edge[i].to;
21 if(!dfn[v]){ //没有更新过的
22 tarjan(v,root);
23 low[x]=min(low[x],low[v]);
24 if(low[v]>=dfn[x]&&x!=root) cut[x]=1; //x不为根的割点判断条件: low[v]>=dfn[x]
25 if(x==root) child++; //若 x为根
26 }
27 else if(x!=root) low[x]=min(low[x],dfn[v]);
28 }
29 if(child>=2&&x==root) cut[x]=1; //x为根的割点判断条件:有2棵及以上的子树
30 }
31 int main()
32 {
33 scanf("%d%d",&n,&m);
34 for(int u,v,i=1;i<=m;i++){
35 scanf("%d%d",&u,&v);
36 add(u,v),add(v,u);
37 }
38 for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
39 for(int i=1;i<=n;i++) if(cut[i]) tot++;
40 printf("%d\n",tot);
41 for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i);
42 return 0;
43 }
View Code