某島

… : "…アッカリ～ン . .. . " .. .
July 17, 2015

BZOJ 1179: [Apio2009]Atm

http://www.lydsy.com/JudgeOnline/problem.php?id=1179

const int N = int(5e5) + 9;
bool _isBar[N], isBar[N];
int _n, n;
int _st;

int dfn[N], low[N], bel[N], sta[N], Time, top; VI con[N];

#define v (*it)
void tarjan(int u){

low[u] = dfn[u] = ++Time;
sta[top++] = u;

if (dfn[v] < dfn[u]){
if (!dfn[v]) tarjan(v);
checkMin(low[u], low[v]);
}
}

if (low[u] == dfn[u]){
int t;
do{
t = sta[--top];
con[n].PB(t);
bel[t] = n;
dfn[t] = INF;
bonus[n] += _bonus[t];
isBar[n] |= _isBar[t];
} while(t != u);
++n;
}
}

void scc(){

REP_1(u, _n) if(!dfn[u]) tarjan(u);

int a = bel[u], b = bel[v];
if (a == b) continue;
}
}

int F[N]; int f(int u){
int &res = F[u];
if (res == -1){
int t = -INF;
res = t >= 0 ? t + bonus[u] : -INF;
}
return res;
}

int main(){

#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif

RD(_n); Rush{
int a, b; RD(a, b); --a, --b;
}
REP(i, _n) RD(_bonus[i]);
--RD(_st); Rush _isBar[RD()-1] = true;

scc();

FLC(F, -1); int st = bel[_st]; F[st] = bonus[st];
int z = 0; REP(i, n) if (isBar[i]) checkMax(z, f(i));

/*REP(i, n){
ECH(it, con[i]) cout << v << " ";
cout << bonus[i] << endl;
}*/

cout << z << endl;
}