首页 > 代码库 > bzoj1179 [Apio2009]Atm
bzoj1179 [Apio2009]Atm
Description
Input
第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数,表示P个有酒吧的路口的编号
Output
输出一个整数,表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。
Sample Input
6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 5
1 4
4
3
5
6
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 5
1 4
4
3
5
6
Sample Output
47
HINT
50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
/* 非递归tarjan要爆栈,实用性不是很强,需要用网上的这个非递归版tarjan */ #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<vector> using namespace std; const int maxn = 500500; struct edge{ int v; int nxt; }e[maxn]; int n,m,s,p,mny[maxn],nmny[maxn]; int head[maxn],cnt; int stop,sta[maxn],dfn[maxn],low[maxn],isin[maxn],indx; int tot; int d[maxn],vis[maxn]; bool inst[maxn]; stack<int> st; vector<int> g[maxn]; int read(){ char ch=getchar(); int x=0,f=1; while(!(ch>=‘0‘&&ch<=‘9‘)){if(ch==‘-‘)f=-1;ch=getchar();}; while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(ch-‘0‘);ch=getchar();}; return x*f; } void ins(int u,int v){ cnt++; e[cnt].v = v; e[cnt].nxt = head[u]; head[u] = cnt; } void input(){ n = read(); m = read(); int u,v; for(int i = 1;i <= m;i++){ u = read(); v = read(); ins(u,v); } for(int i = 1;i <= n;i++) mny[i] = read(); s = read(); p = read(); } void st_psh(int x){ dfn[x] = low[x] = ++indx; inst[x] = true; sta[++stop] = x; st.push(x); } void tarjan(int x){ int t; st_psh(x); while(!st.empty()){ t = st.top(); for(int i = head[t];i;i = e[i].nxt){ if(dfn[e[i].v] == 0){ st_psh(e[i].v); break; } } if(t == st.top()){ for(int i = head[t];i;i = e[i].nxt){ if(dfn[e[i].v] > dfn[t]) low[t] = min(low[e[i].v],low[t]); else if(inst[e[i].v]){low[t] = min(dfn[e[i].v],low[t]);} } if(dfn[t] == low[t]){ ++tot; int j; do{ j = sta[stop--]; inst[j] = false; isin[j] = tot; nmny[tot] += mny[j]; }while(j != t); } st.pop(); } } } void spfa(){ int u,to; queue<int> q; u = isin[s]; d[isin[s]] = nmny[isin[s]]; vis[isin[s]] = true; q.push(isin[s]); while(!q.empty()){ u = q.front(); q.pop(); for(int i = 0;i < g[u].size();i++){ to = g[u][i]; if(d[to] < d[u] + nmny[to]){ d[to] = d[u] + nmny[to]; if(!vis[to]){ vis[to] = true; q.push(to); } } } vis[u] = false; } } void work(){ for(int i = 1;i <= n;i++){ if(!dfn[i]) tarjan(i); } for(int i = 1;i <= n;i++){ for(int j = head[i];j;j = e[j].nxt){ if(isin[i] != isin[e[j].v]){ g[isin[i]].push_back(isin[e[j].v]); //cout<<isin[i]<<" "<<isin[e[j].v]<<endl; } } } spfa(); int qs,ans = 0; while(p--){ qs = read(); ans = max(d[isin[qs]],ans); } cout<<ans; } int main(){ input(); work(); return 0; }
bzoj1179 [Apio2009]Atm
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。