POJ3160FatherChristmasflymouse

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 #include 
  9 #include 
 10 #include <string>
 11 #include <set>
 12 #include 
 13 #define LL long long
 14 #define pii pair
 15 #define INF 0x3f3f3f3f
 16 using namespace std;
 17 const int maxn = 30010;
 18 struct arc{
 19     int to,next;
 20     arc(int x = 0,int y = -1){
 21         to = x;
 22         next = y;
 23     }
 24 };
 25 arc e[maxn*10];
 26 vector<int>g[maxn];
 27 int tot,head[maxn],d[maxn],dfn[maxn],low[maxn],belong[maxn];
 28 int hv[maxn],thv[maxn],scc,idx;
 29 int my[maxn],in[maxn],out[maxn],top,n,m;
 30 bool instack[maxn],inq[maxn];
 31 void add(int u,int v){
 32     e[tot] = arc(v,head[u]);
 33     head[u] = tot++;
 34 }
 35 void tarjan(int u){
 36     dfn[u] = low[u] = ++idx;
 37     my[top++] = u;
 38     instack[u] = true;
 39     for(int i = head[u]; ~i; i = e[i].next){
 40         if(!dfn[e[i].to]){
 41             tarjan(e[i].to);
 42             low[u] = min(low[u],low[e[i].to]);
 43         }else if(instack[e[i].to]) low[u] = min(low[u],dfn[e[i].to]);
 44     }
 45     if(low[u] == dfn[u]){
 46         int v;
 47         scc++;
 48         do{
 49             v = my[--top];
 50             instack[v] = false;
 51             belong[v] = scc;
 52         }while(v != u);
 53     }
 54 }
 55 void init(){
 56     for(int i = 0; i <= n; ++i){
 57         head[i] = -1;
 58         dfn[i] = low[i] = 0;
 59         out[i] = belong[i] = 0;
 60         inq[i] = instack[i] = false;
 61         g[i].clear();
 62         hv[i] = thv[i] = 0;
 63         in[i] = d[i] = 0;
 64     }
 65     tot = idx = scc = 0;
 66 }
 67 void spfa(){
 68     queue<int>q;
 69     q.push(0);
 70     while(!q.empty()){
 71         int u = q.front();
 72         q.pop();
 73         inq[u] = false;
 74         for(int i = g[u].size()-1; i >= 0; --i){
 75             if(d[g[u][i]]  thv[g[u][i]]){
 76                 d[g[u][i]] = d[u] + thv[g[u][i]];
 77                 if(!inq[g[u][i]]){
 78                     inq[g[u][i]] = true;
 79                     q.push(g[u][i]);
 80                 }
 81             }
 82         }
 83     }
 84 }
 85 int main() {
 86     int u,v,w;
 87     while(~scanf("%d %d",&n,&m)){
 88         init();
 89         for(int i = 0; i i)
 90             scanf("%d",hv+i);
 91         for(int i = 0; i i){
 92             scanf("%d %d",&u,&v);
 93             add(u,v);
 94         }
 95         for(int i = 0; i i)
 96             if(!dfn[i]) tarjan(i);
 97         for(int i = 0; i i)
 98             if(hv[i] > 0) thv[belong[i]] += hv[i];
 99         for(int i = 0; i i){
100             for(int j = head[i]; ~j; j = e[j].next){
101                 if(belong[i] == belong[e[j].to]) continue;
102                 g[belong[i]].push_back(belong[e[j].to]);
103                 in[belong[e[j].to]]++;
104                 out[belong[i]]++;
105             }
106         }
107         for(int i = 1; i <= scc; ++i)
108             if(!in[i]) g[0].push_back(i);
109         int ans = 0;
110         spfa();
111         for(int i = 1; i <= scc; ++i)
112             if(!out[i]) ans = max(ans,d[i]);
113         printf("%d\n",ans);
114     }
115     return 0;
116 }