抢掠计划
时间： 1ms 内存：128M
描述：
Siruseri城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个Siruseri银行的ATM取款机。令人奇怪的是，Siruseri的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。 Banditji计划实施Siruseri有史以来最惊天动地的ATM抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的ATM机，最终他将在一个酒吧庆祝他的胜利。 使用高超的黑客技术，他获知了每个ATM机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个ATM机后，该ATM机里面就不会再有钱了。 例如，假设该城中有6个路口，道路的连接情况如下图所示：
市中心在路口1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表示。每个ATM机中可取的钱数标在了路口的上方。在这个例子中，Banditji能抢劫的现金总数为47，实施的抢劫路线是：1-2-4-1-2-3-5。
50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
输入：
第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号。
输出：
输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。
示例输入：
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示例输出：
47
提示：
参考答案（内存最优[26132]）：
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string.h>
#include <string>
#include <set>
#include <queue>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using std::set;
using std::pair;
using std::make_pair;
const int maxN = 500010;
const int SIZE = 0xfffff;
const int MAX = 0x3f3f3f3f;
const int MIN = ~MAX;
struct Edge
{
int v;
Edge *next;
};
Edge *edge1[maxN], *edge2[maxN];
bool marked[maxN], bar[maxN], final[maxN];
int q[maxN], money[maxN], dist[maxN];
int cnt[maxN], DFN[maxN], Low[maxN];
int belong[maxN], stack[maxN];
int n, m, S, P, top, Index, Bcnt, ans, f, r;
inline int getint()
{
int res = 0;
char tmp;
while (!isdigit(tmp = getchar()));
do res = (res << 3) + (res << 1) + tmp - '0';
while (isdigit(tmp = getchar()));
return res;
}
inline void insert2(int u, int v)
{
if (u == v) return;
for (Edge *p = edge2[u]; p; p = p -> next)
if (p -> v == v) return;
Edge *p = new Edge;
p -> v = v;
p -> next = edge2[u];
edge2[u] = p;
return;
}
inline void insert1(int u, int v)
{
Edge *p = new Edge;
p -> v = v;
p -> next = edge1[u];
edge1[u] = p;
return;
}
void readdata()
{
n = getint();
for (m = getint(); m; --m)
{
int u = getint(), v = getint();
insert1(u, v);
}
for (int i = 1; i < n + 1; ++i)
money[i] = getint();
S = getint();
for (P = getint(); P; --P)
bar[getint()] = 1;
return;
}
void tarjan(int u)
{
Low[u] = DFN[u] = ++Index;
marked[stack[++top] = u] = true;
for (Edge *p = edge1[u]; p; p = p -> next)
{
int v = p -> v;
if (!DFN[v])
{
tarjan(v);
Low[u] = min(Low[u], Low[v]);
}
else if (marked[v])
Low[u] = min(Low[u], DFN[v]);
}
if (Low[u] == DFN[u])
{
++Bcnt;
int tmp = u;
do
{
marked[tmp = stack[top--]] = 0;
belong[tmp] = Bcnt;
final[Bcnt] |= bar[tmp];
cnt[Bcnt] += money[tmp];
}
while (tmp != u);
}
return;
}
inline int Spfa()
{
memset(marked, 0, sizeof marked);
memset(dist, ~0x3f, sizeof dist);
int ans = final[belong[S]]
? cnt[belong[S]] : 0;
top = 0;
q[r++] = belong[S];
dist[belong[S]] = cnt[belong[S]];
marked[belong[S]] = 1;
while (f < r)
{
int u = q[f++];
marked[u] = 0;
for (Edge *p = edge2[u]; p; p = p -> next)
if (dist[u] + cnt[p -> v] > dist[p -> v])
{
dist[p -> v] = dist[u] + cnt[p -> v];
if (final[p -> v])
ans = max(ans, dist[p -> v]);
if (!marked[p -> v])
{
marked[p -> v] = 1;
q[r++] = p -> v;
}
}
}
return ans;
}
void work()
{
tarjan(S);
for (int i = 1; i < n + 1; ++i)
for (Edge *p = edge1[i]; p; p = p -> next)
if (belong[p -> v] != belong[i])
insert2(belong[i], belong[p -> v]);
printf("%d\n", Spfa());
return;
}
int main()
{
readdata();
work();
return 0;
}
参考答案（时间最优[8]）：
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string.h>
#include <string>
#include <set>
#include <queue>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using std::set;
using std::pair;
using std::make_pair;
const int maxN = 500010;
const int SIZE = 0xfffff;
const int MAX = 0x3f3f3f3f;
const int MIN = ~MAX;
struct Edge
{
int v;
Edge *next;
};
Edge *edge1[maxN], *edge2[maxN];
bool marked[maxN], bar[maxN], final[maxN];
int q[maxN], money[maxN], dist[maxN];
int cnt[maxN], DFN[maxN], Low[maxN];
int belong[maxN], stack[maxN];
int n, m, S, P, top, Index, Bcnt, ans, f, r;
inline int getint()
{
int res = 0;
char tmp;
while (!isdigit(tmp = getchar()));
do res = (res << 3) + (res << 1) + tmp - '0';
while (isdigit(tmp = getchar()));
return res;
}
inline void insert2(int u, int v)
{
if (u == v) return;
for (Edge *p = edge2[u]; p; p = p -> next)
if (p -> v == v) return;
Edge *p = new Edge;
p -> v = v;
p -> next = edge2[u];
edge2[u] = p;
return;
}
inline void insert1(int u, int v)
{
Edge *p = new Edge;
p -> v = v;
p -> next = edge1[u];
edge1[u] = p;
return;
}
void readdata()
{
n = getint();
for (m = getint(); m; --m)
{
int u = getint(), v = getint();
insert1(u, v);
}
for (int i = 1; i < n + 1; ++i)
money[i] = getint();
S = getint();
for (P = getint(); P; --P)
bar[getint()] = 1;
return;
}
void tarjan(int u)
{
Low[u] = DFN[u] = ++Index;
marked[stack[++top] = u] = true;
for (Edge *p = edge1[u]; p; p = p -> next)
{
int v = p -> v;
if (!DFN[v])
{
tarjan(v);
Low[u] = min(Low[u], Low[v]);
}
else if (marked[v])
Low[u] = min(Low[u], DFN[v]);
}
if (Low[u] == DFN[u])
{
++Bcnt;
int tmp = u;
do
{
marked[tmp = stack[top--]] = 0;
belong[tmp] = Bcnt;
final[Bcnt] |= bar[tmp];
cnt[Bcnt] += money[tmp];
}
while (tmp != u);
}
return;
}
inline int Spfa()
{
memset(marked, 0, sizeof marked);
memset(dist, ~0x3f, sizeof dist);
int ans = final[belong[S]]
? cnt[belong[S]] : 0;
top = 0;
q[r++] = belong[S];
dist[belong[S]] = cnt[belong[S]];
marked[belong[S]] = 1;
while (f < r)
{
int u = q[f++];
marked[u] = 0;
for (Edge *p = edge2[u]; p; p = p -> next)
if (dist[u] + cnt[p -> v] > dist[p -> v])
{
dist[p -> v] = dist[u] + cnt[p -> v];
if (final[p -> v])
ans = max(ans, dist[p -> v]);
if (!marked[p -> v])
{
marked[p -> v] = 1;
q[r++] = p -> v;
}
}
}
return ans;
}
void work()
{
tarjan(S);
for (int i = 1; i < n + 1; ++i)
for (Edge *p = edge1[i]; p; p = p -> next)
if (belong[p -> v] != belong[i])
insert2(belong[i], belong[p -> v]);
printf("%d\n", Spfa());
return;
}
int main()
{
readdata();
work();
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。