【NOIP2016提高A组模拟9.9】爬山

本文主要是介绍【NOIP2016提高A组模拟9.9】爬山，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

国家一级爬山运动员h10今天获得了一张有着密密麻麻标记的地图，在好奇心的驱使下，他又踏上了去爬山的路。
对于爬山，h10有一个原则，那就是不走回头路，于是他把地图上的所有边都标记成了有向边。他决定从点S出发，每到达一个新的节点他就可以获得一定的成就值。同时h10又是一个很珍惜时间的运动员，他不希望这次爬山的成就值白白浪费，所以最后他一定要在一个存档点停下，保存自己的成就值。
请你计算出在此次爬山运动中h10能够得到的最大成就值。保证h10能走到存档点。

Input

第一行两个整数 N，M，表示点数和边数。
接下来 M 行，每行两个整数 u，v，表示u到v有一条有向边(没有自环)。
第 M+2 行 N 个正整数，表示每个点的成就值。
接下来一行两个整数 S，p，表示出发点和存档点个数。
下面一行 p 个整数，表示存档点。

Output

一个正整数，表示最大成就值。

Sample Input

5 7
5 1
3 1
2 5
3 5
4 3
4 2
4 5
7 6 3 2 2
4 3
1 5 2

Sample Output

Data Constraint

对于 30% 的数据， N,M≤1000，并且地图为有向无环图。
对于 100% 的数据， N,M≤500000。（数据有梯度，注意答案的大小）

Solution

这题和以前做过的某道题是几乎一样的
对于无环图，直接SPFA，最后找到最大的一个终点，就行了
那么有环呢？缩环解决
缩环显然是用Tarjan
然而Tarjan一般是要递归的，这里会爆栈，于是打人工栈
不会的点上面的Tarjan

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 501000
#define ll long long
using namespace std;
int n,m,last[N*10],next[N*10],to[N*10],b[N][2],d[N*10],tot=0,bz[N],bz2[N],low[N],dfn[N],p[N],c[N],totot=0,zx[N],zi[N],zk[N],o;
ll a[N],f[N],co[N];
void putin(int x,int y)
{if(x==y) return;next[++tot]=last[x];last[x]=tot;to[tot]=y;
}
void spfa(int s)
{fo(i,1,n) f[i]=-9223372036854775807ll,bz[i]=0;int i=0,j=1;d[1]=s;f[s]=co[s];while(i<j){int q=d[++i];for(int k=last[q];k;k=next[k]){int l=to[k];if(f[l]<f[q]+co[l]){f[l]=f[q]+co[l];if(!bz[l]) bz[l]=1,d[++j]=l;}}bz[q]=0;}
}
void tarjan1()
{int x=zx[o];low[x]=dfn[x]=++tot;p[++p[0]]=x;bz[x]=bz2[x]=1;for(int i=last[x];i;i=next[i]){if(!bz[to[i]]){zk[o]=1;zi[o]=i;zx[++o]=to[i];zk[o]=0;return;} else if(bz2[to[i]]) low[x]=min(low[x],dfn[to[i]]);}if(low[x]==dfn[x]){totot++;for(;p[p[0]+1]!=x;p[0]--) c[p[p[0]]]=totot,bz2[p[p[0]]]=0;}o--;
}
void tarjan2()
{int x=zx[o];low[x]=min(low[x],low[to[zi[o]]]);for(int i=next[zi[o]];i;i=next[i]){if(!bz[to[i]]){zk[o]=1;zi[o]=i;zx[++o]=to[i];zk[o]=0;return;} else if(bz2[to[i]]) low[x]=min(low[x],dfn[to[i]]);}if(low[x]==dfn[x]){totot++;for(;p[p[0]+1]!=x;p[0]--) c[p[p[0]]]=totot,bz2[p[p[0]]]=0;}o--;
}
void tarjan(int x)
{zx[++o]=x;zk[o]=0;zi[o]=0;while(o>0){if(zk[o]==0) tarjan1(); else tarjan2();}
}
int main()
{scanf("%d%d",&n,&m);fo(i,1,m) {scanf("%d%d",&b[i][0],&b[i][1]);putin(b[i][0],b[i][1]);}fo(i,1,n) scanf("%lld",&a[i]);int s,q;scanf("%d%d",&s,&q);ll ans=0;tot=0;fo(i,1,n) if(!bz[i]) tarjan(i); fo(i,1,n) co[c[i]]+=a[i];memset(last,0,sizeof(last));tot=0;fo(i,1,m) putin(c[b[i][0]],c[b[i][1]]);spfa(c[s]);for(;q;q--){int x;scanf("%d",&x);ans=ans<f[c[x]]?f[c[x]]:ans;}printf("%lld",ans);
}