如题
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<queue> 5 #include<vector> 6 #include<cstdio> 7 using namespace std; 8 9 const int Maxn = 1e4+10,Maxm = 1e5+10; 10 11 struct Edge{ 12 int to,ne; 13 }edges[Maxm]; 14 15 vector<int> scc[Maxn],g[Maxn]; 16 int first[Maxn],dfn[Maxn],low[Maxn],stack[Maxn],ins[Maxn],inscc[Maxn]; 17 int val[Maxn],sval[Maxn],ind[Maxn],f[Maxn]; 18 int n,m,cnte,cntv,cntscc,top; 19 20 int read(){ 21 int a = 0;char l = ' ',c = getchar(); 22 while(c < '0'||c > '9')l = c,c = getchar(); 23 while('0' <= c&&c <= '9')a = a*10+c-'0',c = getchar(); 24 if(l == '-')return -a;return a; 25 } 26 27 void add_edge(int fr,int to){ 28 edges[++cnte] = (Edge){to,first[fr]}; 29 first[fr] = cnte; 30 } 31 32 void dfs(int x){//printf("dfs::%d ",x); 33 low[x] = dfn[x] = ++cntv; 34 ins[x] = 1,stack[++top] = x; 35 for(int i = first[x];i;i = edges[i].ne){ 36 Edge e = edges[i]; 37 if(!dfn[e.to])dfs(e.to),low[x] = min(low[x],low[e.to]); 38 else if(ins[e.to])low[x] = min(low[x],dfn[e.to]); 39 } 40 if(dfn[x] == low[x]){ 41 int y = 0; 42 cntscc++; 43 while(y != x){ 44 y = stack[top--]; 45 ins[y] = 0,inscc[y] = cntscc; 46 scc[cntscc].push_back(y); 47 } 48 } 49 } 50 51 int ans = 0; 52 void toposort(){ 53 queue<int> q; 54 for(int i = 1;i <= cntscc;i++)if(!ind[i])q.push(i); 55 while(!q.empty()){ 56 int u = q.front();q.pop(); 57 f[u] += sval[u];//printf("%d ",u); 58 ans = max(ans,f[u]); 59 for(int i = 0;i < g[u].size();i++){ 60 int v = g[u][i]; 61 ind[v]--; 62 f[v] = max(f[v],f[u]); 63 if(!ind[v])q.push(v); 64 } 65 } 66 } 67 68 int main(){ 69 cin >> n >> m; 70 for(int i = 1;i <= n;i++)val[i] = read(); 71 for(int i = 1;i <= m;i++)add_edge(read(),read()); 72 for(int i = 1;i <= n;i++)if(!dfn[i])dfs(i);//putchar(' '); 73 for(int i = 1;i <= cntscc;i++){ 74 for(int j = 0;j < scc[i].size();j++){ 75 int u = scc[i][j]; 76 sval[i] += val[u]; 77 for(int k = first[u];k;k = edges[k].ne){ 78 Edge e = edges[k]; 79 if(inscc[e.to] == i)continue; 80 g[i].push_back(inscc[e.to]); 81 ind[inscc[e.to]]++; 82 } 83 } 84 } 85 86 // for(int i = 1;i <= n;i++)printf("%d:%d ",i,inscc[i]);putchar(' '); 87 // for(int i = 1;i <= cntscc;i++)printf("%d:%d ",i,sval[i]);putchar(' '); 88 89 toposort(); 90 cout << ans; 91 return 0; 92 }