BZOJ1179【APIO2009】ATM < Tarjan >

Problem

【APIO2009】ATM

$\mathrm{Time\;Limit:\;15\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

$\mathrm{Siruseri}$城中的道路都是单向的。不同的道路由路口连接。按照法律规定，在每个路口都设立了一个$\mathrm{Siruseri}$银行的$\mathrm{ATM}$取款机。令人奇怪的是，$\mathrm{Siruseri}$的酒吧都设在路口，虽然并不是每个路口都设有酒吧。
$\mathrm{Banditiji}$计划实施$\mathrm{Siruseri}$有史以来最惊天动地的$\mathrm{ATM}$抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的$\mathrm{ATM}$机，最终他将在一个酒吧庆祝他的胜利。
使用高超的黑客技术，他获知了每个$\mathrm{ATM}$机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某酒吧时最多能抢劫的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫某个$\mathrm{ATM}$机后，该$\mathrm{ATM}$机就不会再有钱了。

Input

第一行包含两个整数$N$、$M$。$N$表示路口的个数，$M$表示道路条数。接下来$M$行，每行两个整数，这两个整数都在$1$到$N$之间，第$i+1$行的两个整数表示第i条道路的起点和终点的路口编号。接下来$N$行，每行一个整数，按顺序表示每个路口处的$\mathrm{ATM}$机中的钱数。接下来一行包含两个整数$S$、$P$，$S$表示市中心的编号，也就是出发的路口。$P$表示酒吧数目。接下来的一行中有$P$个整数，表示$P$个有酒吧的路口的编号。

Output

输出一个整数，表示$\mathrm{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

Sample Output

47

HINT

$30\%$的输入保证$N, M\le 3000$。
$100\%$的输入保证$N, M\le 500000$。
每个$\mathrm{ATM}$机中可取的钱数为一个非负整数且不超过$4000$。
输入数据保证你可以从市中心沿着$\mathrm{Siruseri}$的单向的道路到达其中的至少一个酒吧。

标签：Tarjan SPFA

Solution

题面有一种莫名其妙的喜感
这道题是我的第一道$\mathrm{APIO}$题（虽然是水题）
首先，很容易看出要tarjan缩点。题目说城市的路是单向边，而且可以经过任意一点任意多次，所以走到强连通分量，这个强连通分量的所有点都可以到达，所有$\mathrm{ATM}$机都可以抢。
于是我们先缩点，顺带记录每个分量的$\mathrm{ATM}$机价值总和，并统计每个分量有没有酒吧，即能否作为停止点。然后跑一遍SPFA，找以所有带酒吧的分量为终点的最长路即可。
五十行随便写完，数据无坑。

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#define MAX_N 500000
using namespace std;
int n, m, s, p, c[MAX_N+5], end[MAX_N+5], endc[MAX_N+5], dfn[MAX_N+5], low[MAX_N+5], id[MAX_N+5], sz[MAX_N+5], ind, cnt;
vector <int> G[MAX_N+5], E[MAX_N+5];
stack <int> sta;    bool insta[MAX_N+5];
void tarjan(int u) {
    dfn[u] = low[u] = ++ind, sta.push(u), insta[u] = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!dfn[v])	tarjan(v), low[u] = min(low[u], low[v]);
        else if (insta[v])	low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        cnt++;
        for (int i = sta.top(); ; i = sta.top()) {
            id[i] = cnt, sz[cnt] += c[i], insta[i] = false;
            sta.pop();	if (i == u)	break;
        }
    }
}
queue <int> que;    bool inque[MAX_N+5];	int f[MAX_N+5], ans;
void SPFA() {
    f[s] = sz[s], que.push(s), inque[s] = true;
    while (!que.empty()) {
        int u = que.front();	que.pop(), inque[u] = false;
        for (int i = 0; i < E[u].size(); i++) {
            int v = E[u][i];	if (f[v] > f[u]+sz[v])	continue;
            f[v] = f[u]+sz[v];	if (!inque[v])	que.push(v), inque[v] = true;
            if (endc[v])	ans = max(ans, f[v]);
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    while (m--) {int u, v;	scanf("%d%d", &u, &v), G[u].push_back(v);}
    for (int i = 1; i <= n; i++)	scanf("%d", &c[i]);
    scanf("%d%d", &s, &p);
    while (p--) {int x;	scanf("%d", &x), end[x] = 1;}
    for (int i = 1; i <= n; i++)	if (!dfn[i])	tarjan(i);
    for (int i = 1; i <= n; i++)	endc[id[i]] |= end[i];
    for (int u = 1; u <= n; u++)	for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];	if (id[u] != id[v])	E[id[u]].push_back(id[v]);}
    s = id[s], SPFA();
    printf("%d", ans);
    return 0;
}