<span>hihocoder1185 连通性·三</span>
输入
第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000
第2行：N个正整数，第i个整数表示第i个牧场的草量w[i]。1≤w[i]≤100,000
第3..M+2行：2个正整数，u,v。表示存在一条从u到v的单向路径。1≤u,v≤N
输出
第1行：1个整数，最多能够吃到的牧草数量。
6 6 2 4 3 5 4 4 1 2 2 4 1 3 3 5 3 6 6 3</dd> <dt> 样例输出 </dt> <dd>
13
/* *********************************************** Author :devil Created Time :2016/6/9 15:45:46 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; const int N=20010; int dfn[N],low[N],Stack[N],belong[N],cou,ed,cnt,n; int w[N],ans[N]; bool instack[N]; vector<int>eg[N],eg2[N]; void dfs(int u) { dfn[u]=low[u]=cou++; Stack[ed++]=u; instack[u]=1; for(int i=0; i<eg[u].size(); i++) { int v=eg[u][i]; if(!dfn[v]) { dfs(v); low[u]=min(low[u],low[v]); } else if(instack[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { cnt++; int j; do { j=Stack[--ed]; belong[j]=cnt; instack[j]=0; } while(j!=u); } } int dfs2(int u,int sum) { int mx=sum; for(int i=0; i<eg2[u].size(); i++) mx=max(mx,dfs2(eg2[u][i],sum+ans[eg2[u][i]])); return mx; } void print() { for(int i=1; i<=n; i++) for(int j=0; j<eg[i].size(); j++) if(belong[i]!=belong[eg[i][j]]) eg2[belong[i]].push_back(belong[eg[i][j]]); for(int i=1; i<=n; i++) ans[belong[i]]+=w[i]; printf("%d\n",dfs2(belong[1],ans[belong[1]])); } void init() { cou=1;ed=0;cnt=0; for(int i=1;i<=n;i++) { eg[i].clear(); eg2[i].clear(); dfn[i]=ans[i]=instack[i]=0; } } int main() { //freopen("in.txt","r",stdin); int m,u,v; while(~scanf("%d%d",&n,&m)) { init(); for(int i=1; i<=n; i++) scanf("%d",&w[i]); for(int i=0; i<m; i++) { scanf("%d%d",&u,&v); eg[u].push_back(v); } for(int i=1; i<=n; i++) if(!dfn[i]) dfs(i); print(); } return 0; }
</dd> </dl>
