bzoj 1179

题意:给你一个有向图,每个点有一个权值,有一个起点和q个终点,没经过一个点加上这个点的权值,让你选一条路,问你最大值是多少。

思路:tarjan强连通缩个点, 然后在拓扑图上dp一下就好啦, 注意第二次建图建反向边会好一点。

 #include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int> using namespace std; const int N=5e5+;
const int M=1e4+;
const int inf=0x3f3f3f3f;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9 + ; struct edge {
int from, to, nx;
}e[N];
bool bar[N], flag[N], in[N], ok[N];
int n, m, tot, cnt, S, p, idx, top, head[N], a[N], sum[N], dfn[N], low[N], id[N], f[N], st[N]; vector<int> edge[N];
void add(int from, int to) {
e[tot].from = from;
e[tot].to = to;
e[tot].nx = head[from];
head[from] = tot++;
} void tarjan(int u) {
++idx;
dfn[u] = low[u] = idx;
st[top++] = u; in[u] = true;
for(int i = head[u]; ~i; i = e[i].nx) {
int v = e[i].to;
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if(in[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]) {
cnt++;
while() {
int now = st[--top];
in[now] = false;
id[now] = cnt;
if(now == u) break;
}
}
} int dp(int u) {
if(f[u] != -) return f[u];
f[u] = ;
for(int i = ; i < edge[u].size(); i++) {
int v = edge[u][i];
int ret = dp(v);
if(ok[v]) {
ok[u] = true;
f[u] = max(f[u], f[v]);
}
}
if(!ok[u]) return f[u];
return f[u] = f[u] + sum[u];
}
int main() {
memset(head, -, sizeof(head));
memset(f, -, sizeof(f));
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
int from, to; scanf("%d%d", &from, &to);
add(from, to);
}
for(int i = ; i <= n; i++)
scanf("%d", &a[i]); scanf("%d%d", &S, &p);
for(int i = ; i <= p; i++) {
int x; scanf("%d", &x);
flag[x] = true;
}
for(int i = ; i <= n; i++) {
if(!dfn[i]) tarjan(i);
}
for(int i = ; i <= n; i++) {
sum[id[i]] += a[i];
bar[id[i]] |= flag[i];
}
for(int i = ; i < tot; i++) {
int u = e[i].from, v = e[i].to;
if(id[u] != id[v]) {
edge[id[v]].push_back(id[u]);
}
}
S = id[S];
ok[S] = true;
int ans = ;
for(int i = ; i <= cnt; i++) {
if(bar[i]) {
ans = max(ans, dp(i));
}
}
printf("%d\n", ans);
return ;
}
/*
*/
上一篇:网络的FIN_WAIT_2状态解释和分析


下一篇:html,css.javascript