首页 > 代码库 > CDOJ 1431 不是图论 Label：Tarjan || Kosarajn

CDOJ 1431 不是图论 Label：Tarjan || Kosarajn

2024-08-15 13:52:33   222人阅读

E - 不是图论
Time Limit:1000MS     Memory Limit:65535KB     64bit IO Format:%lld & %llu

Description

给出一个nn个点，mm条边的有向图。每个点上有分值，经过这个点时可以获得一定的分数。

一个点可以经过多次，但是一个点上的分数只能获得一次。

问最多能获得多少分数，起点任选。

1<=nn<=30000,1<=mm<=100000

Input

输入包含多组数据

每组数据第一行为nn，mm

接下来nn行，每行有一个数，表示第ii个节点的分值。

接下来mm行，每行有两个数aa、bb，表示有一条从aa到bb的有向边

Output

每组数据输出一行，每行仅有一个整数：可以获得的最多的分数。

Sample Input

5 5 
1 1 1 2 3 
1 2 
2 3 
3 1 
1 4 
1 5 
5 3 
1 2 3 4 5 
1 2 
1 3 
4 5

Sample Output

6 
9

代码

 1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<vector> 5 #include<cstdio> 6 #include<queue> 7 const int MAXN=30010; 8 using namespace std; 9 10 vector<int> G[MAXN],rG[MAXN],Next[MAXN],vec;11 int N,m,f[MAXN],vis[MAXN],ref_nod[MAXN],cost_ref[MAXN],cost_nod[MAXN];12 13 void init_(){14     memset(vis,0,sizeof(vis));15     memset(f,0,sizeof(f));16     memset(ref_nod,0,sizeof(ref_nod));17     memset(cost_ref,0,sizeof(cost_ref));18     memset(cost_nod,0,sizeof(cost_nod));19     for(int i=0;i<=N;i++){20         G[i].clear();21         rG[i].clear();22         Next[i].clear();23         vec.clear();24     }25 }26 27 void rdfs(int x,int k){28     vis[x]=1;29     ref_nod[x]=k;30     cost_ref[k]+=cost_nod[x];31     for(int i=0;i<rG[x].size();i++){32         int to=rG[x][i];33         if(!vis[to]) rdfs(to,k);34         if(ref_nod[to]!=k) Next[k].push_back(ref_nod[to]);35     }36 }37 38 void dfs(int x){39     vis[x]=1;40     for(int i=0;i<G[x].size();i++){41         int to=G[x][i];42         if(!vis[to]) dfs(to);43     }44     vec.push_back(x);45 }46 47 int Sum(int x){48     vis[x]=1;49     if(f[x]>0) return f[x];50     int tmp=0;51     for(int i=0;i<Next[x].size();i++){52         tmp=max(tmp,Sum(Next[x][i]));53     }54     return f[x]=tmp+cost_ref[x];55 }56 57 void scc(){58     int k=1;59     memset(vis,0,sizeof(vis));60     for(int i=1;i<=N;i++)61         if(!vis[i]) dfs(i);62     /**/63     memset(vis,0,sizeof(vis));64     for(int i=vec.size()-1;i>=0;i--)65         if(!vis[vec[i]]) rdfs(vec[i],k++);66     67     int tot=0;68     memset(vis,0,sizeof(vis));69     for(int i=1;i<k;i++){70         if(!vis[i]) tot=max(tot,Sum(i));71     }72     printf("%d\n",tot);73 }74 75 int main(){76 //    freopen("01.in","r",stdin);77     while(scanf("%d%d",&N,&m)==2){78         init_();79         for(int i=1;i<=N;i++) scanf("%d",&cost_nod[i]);80         for(int i=1;i<=m;i++){81             int x,y;82             scanf("%d%d",&x,&y);83             G[x].push_back(y);84             rG[y].push_back(x);85         }86         scc();87     }88     return 0;89 }

三个类似dfs的玩意儿，记得初始化~

Next记录该强联通的下一个强联通

ref就是各种映射

CDOJ 1431 不是图论 Label：Tarjan || Kosarajn


联系
我们