P3387 【模板】缩点

题目描述

给定一个 n 个点 m* 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 n,m*

第二行 n* 个整数，依次代表点权

第三至 m+2 行，每行两个整数 u,v，表示一条 u→v 的有向边。

输出格式

共一行，最大的点权之和。

输入输出样例

输入 #1

1
2
3
4
2 2
1 1
1 2
2 1

输出 #1

1
2

tarjan 缩点模板…

对于每一个强连通分量，指定一个节点 $u_i （dfn[u_i]==low[u_i]）$的点 ,并且$w[u_i]=sum(w[v_i]）$,

遍历所有的边（u，v），如果 u，v 属于不同的强连通分量 $ i,j$，则在该强连通分量的 $ u_i , u_j$ 之间连边；

可能会连重复的边？看存储方式处理一下，或者不处理…

一种可能的情况 ： 强连通分量的总的代价 等于0 ，所以是不能以 w[u] 是否等于 0 来判断该点是否是最后树中的节点的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
int a[MAX],n,m,u,v,ans;
int indeg[MAX],d[MAX],rt[MAX];
struct node{
	int to,next;
}e[MAX*10*2],e2[MAX*10*2];
int head[MAX],head2[MAX],tot=0,tot2=0;
void addedge(int u,int v){
	e[tot].to = v;
	e[tot].next=head[u];
	head[u]=tot++; 
}
void addedge2(int u,int v){
	e2[tot2].to = v;
	e2[tot2].next=head2[u];
	head2[u]=tot2++; 
}
int dfn[MAX],low[MAX],color[MAX],num[MAX],Stack[MAX];	
bool instack[MAX];
int ind,scc,top;
void tarjan(int u,int fa){
	int v;
	dfn[u]=low[u]=++ind;
	Stack[top++]=u;
	instack[u]=true;
	for(int i=head[u];i!=-1;i=e[i].next){
		v = e[i].to;
		//if(v==fa) continue; //无向图 
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}else if(instack[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		scc++;
		rt[scc]=u;  //记录此联通块的缩点 
		do{
			v=Stack[--top];
			instack[v]=false;
			color[v]=scc; //标记属于哪一个强连通分量
			num[scc]++;
			if(u!=v){
				a[u]+=a[v]; // 缩点 
				a[v]=0;	
			}
		}while(v!=u);
	} 
}
void solve(){
	mem(instack,0);
	mem(num,0);
	mem(dfn,0);
	ind=scc=top=0;
	fi(i,1,n+1)
		if(!dfn[i])
			tarjan(i,-1);
}
void topo(){
	queue<int>q;
	fi(i,1,n+1)
		if(!indeg[i]) {
			d[i]=a[i];
			q.push(i); //i 点没有被"缩"掉 
		} 
	while(!q.empty()){
		int u= q.front();
		q.pop();
		// todo 记录 
		for(int i=head2[u];i!=-1;i=e2[i].next){
			int v= e2[i].to;
			d[v]=max(d[v],d[u]+a[v]);
			if(--indeg[v]==0) q.push(v);
		}
	} 
} 
int main(){
	freopen("in","r",stdin);
	mem(head,-1);mem(head2,-1);
	sf(n);sf(m);
	fi(i,1,n+1)
		sf(a[i]);
	fi(i,0,m){
		sf(u);sf(v);
		addedge(u,v);
	}
	solve();
	fi(u,1,n+1){
		for(int i=head[u];i!=-1;i=e[i].next){
			int v=e[i].to;
			if(color[u]!=color[v] ){ //收缩后的点才连边 
				indeg[rt[color[v]]]++;
				addedge2(rt[color[u]],rt[color[v]]);
			}
		}
	} 
	topo();
	fi(i,1,n+1){
		ans = max(ans,d[i]);
	}
	pf(ans);
	return 0;
}