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
| #include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std ;
const int maxn = 100005 ;
int n , m ;
int head[maxn] , val[maxn] , nex[maxn] , cnt , to[maxn] , group[10004] ;
int tot , ind , a[10004] , stac[10004] , dfn[10004] , vis[10004] , low[10004] ;
queue < int > Q[10004] ; int col , in[10004] , new_val[10004] ;
int ans[10004] , num ;
void add ( int x , int y ) { nex[++cnt] = head[x] ; head[x] = cnt ; to[cnt] = y ; }
void Tarjan ( int u ) {
dfn[u] = low[u] = ++ tot ; vis[u] = 1 ; stac[++ind] = u ;
for ( int i = head[u] ; i ; i = nex[i] ) {
if ( ! dfn[to[i]] ) {
Tarjan ( to[i] ) ;
low[u] = min ( low[u] , low[to[i]] ) ;
}
else if ( vis[to[i]] ) {
low[u] = min ( low[u] , low[to[i]] ) ;
}
}
if ( low[u] == dfn[u] ) {
int v ; col ++ ;
while ( v = stac[ind--] ) {
Q[col].push ( v ) ; group[v] = col ;
vis[v] = 0 ;
if ( v == u ) break ;
}
}
}
void dfs ( int x , int val ) {
int flag = 0 ;
for ( int i = head[x] ; i ; i ++ ) {
flag = 1 ;
dfs ( to[i] , val + new_val[to[i]] ) ;
}
if ( ! flag ) {
ans[++num] = val ;
}
}
void topo ( ) {
for ( int i = 1 ; i <= col ; i ++ ) {
if ( in[i] == 0 ) {
dfs ( i + n , new_val[i] ) ;
}
}
}
bool cmp ( int x , int y ) { return x > y ; }
int main ( ) {
scanf ( "%d%d" , & n , & m ) ;
for ( int i = 1 ; i <= n ; i ++ ) scanf ( "%d" , & a[i] ) ;
while ( m -- ) {
int x , y ; scanf ( "%d%d" , & x , & y ) ;
add ( x , y ) ;
}
for ( int i = 1 ; i <= n ; i ++ ) {
if ( ! dfn[i] ) Tarjan ( i ) ;
}
for ( int i = 1 ; i <= col ; i ++ ) {
int new_node = i + n , val = 0 ;
while ( ! Q[i].empty ( ) ) {
int x = Q[i].front ( ) ; Q[i].pop ( ) ; val += a[x] ;
for ( int j = head[x] ; j ; j = nex[j] ) {
if ( group[to[j]] == group[x] ) continue ;
add ( new_node , group[to[j]] + n ) ;
in[to[j]] ++ ;
}
}
new_val[i] = val ;
}
topo ( ) ;
sort ( ans + 1 , ans + 1 + num , cmp ) ;
printf ( "%d" , ans[1] ) ;
return 0 ;
}
|
