最优贸易

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 tarjan

..图是一个有环图,因为是单向边，缩点，成有向无环图后，每一个强连通分量记录，内部最大值，最小值.

题目必须从1点出发，缩点后，建立新图，为拓扑图，无法从1到达的点全部删除;

从一点出发，进行拓扑操作，若a->b则，a的值可以更新b

输出终点值即可；
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=2000100;
const int INF=9999999999;
int cnt,head[N],n,m,timestamp;
int dfn[N];//时间戳
int low[N];
int stk[N],top,in_stk[N];//栈
int scc_cnt;//分量数
int Size[N];//强连通分量点的个数
int id[N];//强连通分量
int dout[N];//缩点后的出度
int din[N];//缩点后的入度
int c[N];
int maxv[N],minv[N];
struct edge
{
    int to,nx;
};
edge ed[N*10];
void add(int a,int b)
{
    ed[++cnt].to=b;
    ed[cnt].nx=head[a];
    head[a]=cnt;
}
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=head[u];i!=-1;i=ed[i].nx){
        int j=ed[i].to;
        if(!dfn[j]){
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]){
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u]){
        int y=0;
        ++scc_cnt;//强连通分量总数+1
        do{
            y=stk[top--];//取栈顶元素y
			maxv[scc_cnt]=max(maxv[scc_cnt],c[y]);
			minv[scc_cnt]=min(minv[scc_cnt],c[y]);	
            in_stk[y]=false;//则y不再在栈中
            id[y]=scc_cnt;//点y在此连通图
            Size[scc_cnt]++;//第scc_cnt个连通块点数+1
        }while(y!=u);
    }
}
int ans[N];
void bfs(){
	for(int i=1;i<=scc_cnt;i++){
	maxv[i+n]=maxv[i];
	minv[i+n]=minv[i];
	head[n+i]=-1;
	ans[n+i]=maxv[i]-minv[i];
}
//统计新图中点的出度 
    for(int i=1;i<=n;i++){//判断i到k是不是在一个分量中
        for(int j=head[i];j!=-1;j=ed[j].nx){
            int k=ed[j].to;
            int a=id[i],b=id[k];
//a,b不为一个连通分量
            if(a!=b) {
//缩点后的有向无环图,建立新图  
//拓扑排序图       
            add(a+n,b+n);	
			din[b+n]++;}
//a出度+1  dout[a] += i→k
        }
    }
int s=n+id[1];//起点
 queue<int>q;
 //缩点后的有向无环图,无法从S到达的点全删除
  for(int i = 1; i <= scc_cnt; i ++) 
        if(!din[n+i]&&n+i!=s)
            q.push(n+i);
  while(q.size()) 
    {
        int key = q.front();
        q.pop();
        for(int i = head[key]; i!=-1; i = ed[i].nx)
        {
            int j = ed[i].to;
            din[j] --;
            if(!din[j]) q.push(j);
        }               
    }  
 
 q.push(s);//起点开始拓扑排序
    while(q.size())
    {
        int key=q.front();//key后面的点可以更新
        q.pop();
		ans[key]=max(ans[key],maxv[key]-minv[key]);
        for(int i = head[key]; i!=-1; i = ed[i].nx)
        {
            int j = ed[i].to;
//传递性
			ans[j]=max(ans[j],ans[key]);
            minv[j]=min(minv[j],minv[key]);
            din[j] --;
            if(!din[j]) q.push(j);
        }           
    } 
//必须到达终点
cout<<ans[n+id[n]];
}
void solve()
{   cnt=0;top=0;timestamp=0;cin>>n>>m;
    for(int i=1;i<=n;i++) {
maxv[i]=-INF,minv[i]=INF;
	head[i]=-1;dfn[i]=0;}
for(int i=1;i<=n;i++) cin>>c[i];
    while(m--){
        int a,b,c;cin>>a>>b>>c;
		if(c==1)
        add(a,b);//有向图
		else{
		add(a,b),add(b,a);
		}
    }
    //缩点，把所有强连通分量缩成一个点
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
	bfs();//进行拓扑排序
}
signed main()
{
    ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
    solve();
    return 0;
}