P3627 [APIO2009] 抢掠计划

标签：抢掠 int v0 dfn push APIO2009 P3627 id dis

从起点S到终点T，求一条路线获得最多的收益（ 每个点收益a[i] ) , 可以重复通过路和点

 

裸题

 
#include <bits/stdc++.h>
using namespace std ;
 const int N=5e5+2;
 int n,m,pool,a[N];
 int low[N],dfn[N];
 
 int kcnt,id[N];
 int f[N],val[N];
 
 vector<int> g[N],vc[N];
 stack<int> st;
 
 void tar(int x){
     dfn[x]=low[x]=++pool; st.push(x);
     int i,y;
     for(i=0;i<g[x].size();i++){
          y=g[x][i];
          if(!dfn[y]) tar(y),low[x]=min(low[x],low[y]);
          else if(!id[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        kcnt++;
        do{
            y=st.top(); st.pop();
            id[y]=kcnt; 
        }while(y!=x);
    }
 }
 
 int dis[N],vis[N];
 
void spfa(int v0){
    queue<int> q;
     memset(dis,0x3f3f3f3f,sizeof(dis)); dis[v0]= -val[v0];
     q.push(v0);
     vis[v0]=1;
     
     int i,x,y,z;
     while(q.empty()==0){
           x=q.front(),q.pop(); vis[x]=0;
           //cout<<"www "<<x<<endl;
           
           for(i=0;i<vc[x].size();i++){
             y=vc[x][i]; z= -val[y];
          if(dis[x]+z<dis[y]){
            dis[y]=dis[x]+z;
            if(!vis[y]) vis[y]=1,q.push(y);    
          }
        }
    } 
 }
  
 int main(){
     int i,j,x,y; 
      cin>>n>>m; 
      for(i=1;i<=m;i++) cin>>x>>y,g[x].push_back(y);
      for(i=1;i<=n;i++) cin>>a[i];
    
      for(i=1;i<=n;i++) if(!dfn[i]) tar(i);
      for(i=1;i<=n;i++) val[id[i]]+=a[i];
      
      for(i=1;i<=n;i++)
       for(j=0;j<g[i].size();j++){
             x=id[i],y=id[g[i][j]];
             if(x!=y) vc[x].push_back(y);
       }
       int S,E;
       cin>>S>>E;
      spfa(id[S]);
    
    int  t=0;
    while(E--){
        cin>>i; t=max(t,-dis[id[i]]);
    }
    cout<<t<<'\n';
 }
 
 

 

标签：抢掠,int,v0,dfn,push,APIO2009,P3627,id,dis
From： https://www.cnblogs.com/towboa/p/16926793.html