LYDSY 1179
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
const int maxn = 500010;
int n, m, s, p;
struct Graph
{
int head[maxn], next[maxn], to[maxn], rnk[maxn], ecnt;
bool ispub[maxn];
inline void addEdge(int f, int t)
{
ecnt++;
next[ecnt] = head[f];
head[f] = ecnt;
to[ecnt] = t;
}
} g1, g2;
int low[maxn], dfn[maxn], scc[maxn], scccnt, idx, st[maxn], top, dis[maxn], que[maxn << 2];
bool inq[maxn];
void tarjan(int u)
{
low[u] = dfn[u] = ++idx;
st[top++] = u;
for (int i = g1.head[u]; i; i = g1.next[i])
if (!dfn[g1.to[i]])
tarjan(g1.to[i]), low[u] = min(low[u], low[g1.to[i]]);
else if (!scc[g1.to[i]])
low[u] = min(low[u], dfn[g1.to[i]]);
if (dfn[u] == low[u])
{
scccnt++;
do
scc[st[--top]] = scccnt;
while (st[top] != u);
}
}
void spfa()
{
int h, t;
h = t = 0;
que[t++] = s;
dis[s] = g2.rnk[s];
inq[s] = true;
for (int x = 0; h ^ t; inq[que[h++]] = false)
for (int i = g2.head[x = que[h]]; i; i = g2.next[i])
if (dis[g2.to[i]] < g2.rnk[g2.to[i]] + dis[x])
{
dis[g2.to[i]] = g2.rnk[g2.to[i]] + dis[x];
if (!inq[g2.to[i]]) inq[que[t++] = g2.to[i]] = true;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; i++)
{
scanf("%d%d", &x, &y);
g1.addEdge(x, y);
}
for (int i = 1; i <= n; i++) scanf("%d", &g1.rnk[i]);
scanf("%d%d", &s, &p);
for (int i = 0, x; i < p; i++)
scanf("%d", &x), g1.ispub[x] = true;
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++)
{
if (g1.ispub[i]) g2.ispub[scc[i]] = true;
g2.rnk[scc[i]] += g1.rnk[i];
}
for (int i = 1; i <= n; i++)
for (int j = g1.head[i]; j; j = g1.next[j])
if (scc[i] != scc[g1.to[j]])
g2.addEdge(scc[i], scc[g1.to[j]]);
s = scc[s];
spfa();
int ans = 0;
for (int i = 1; i <= scccnt; i++)
if (g2.ispub[i])
ans = max(ans, dis[i]);
printf("%d", ans);
return 0;
}