题解 P3627 【[APIO2009]抢掠计划】

· · 题解

原题链接【[APIO2009]抢掠计划】

缩点，水题一道~~

题意

    大概就是要求一个从 1 开始的路径，

    要求结束的一个点是有酒吧，

    路径上点可重复经过，但同一个点的点权只计算一次。

这一看就是缩点了啦

可重复经过~~，

这句话经常就是我们判断一道图上的题是否就是 tarjan 水题的标准

那么本题，缩完点了，建完新图了，然后呢~~

一个简单的想法是在新图上跑一边最长路（和最短路几乎一样）

当然你也可以换成 dp , 或者记搜什么的

然后在所有的有酒吧的连通块里选择一个最优的

新问题来了，怎么跑最短路

点权转边权~~

怎么个转法？

我觉得我的思路不错，因此发了这篇题解

拆点，把一个点拆成两个点，该边边权即为该点点权

然后跑 spfa 最长路就好了

给出代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;
const int maxn = 5e5 + 10;
const int INF = 1 << 25;

inline int read() {
    char c = getchar(); int x = 0, f = 1;
    for (; c > '9' || c < '0'; c = getchar()) if (c == '-') f = -1;
    for (; c >='0' && c <='9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x * f;
}

int a[maxn], id[maxn], sum[maxn], stack[maxn], top, gg, k;
int dis[maxn << 1], ver[maxn], nxt[maxn], head[maxn], tot;
vector <int> h[maxn << 1], hh[maxn << 1];
int p[maxn], dfn[maxn], low[maxn], cnt;
bool ins[maxn], vis[maxn << 1];
int n, m, u, v, S, P, ans;
queue <int> q;

void add_edge () {
    u = read(), v = read();
    ver[++ tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
}

void tarjan (int x) {
    dfn[x] = low[x] = ++ cnt;
    stack[++ top] = x;
    ins[x] = 1;
    for (register int i = head[x]; i; i = nxt[i]) {
        if (!dfn[ver[i]])
            tarjan (ver[i]), low[x] = min (low[x], low[ver[i]]);
        else if (ins[ver[i]])
            low[x] = min (low[x], dfn[ver[i]]);
    }
    if (dfn[x] == low[x]) {
        ++ gg;
        do {
            k = stack[top --];
            ins[k] = 0;
            id[k] = gg;
            sum[gg] += a[k];
        } while (x != k);
    }
}

void djj () {
    n = read(), m = read();
    for (; m; m --)
        add_edge ();
    for (register int i = 1; i <= n; i ++)
        a[i] = read();
    for (register int i = 1; i <= n; i ++)
        if (!dfn[i]) tarjan (i);
    S = read(), P = read();
    for (register int i = 1; i <= P; i ++)
        p[i] = read();
}

void lxy () {
    for (register int i = 1; i <= n; i ++)
        for (register int j = head[i]; j; j = nxt[j])
            if (id[i] != id[ver[j]])
                h[id[i] + gg].push_back (id[ver[j]]), hh[id[i] + gg].push_back (0);
    for (register int i = 1; i <= gg; i ++)
        h[i].push_back (i + gg), hh[i].push_back (sum[i]);
    memset (dis, - INF, sizeof dis);
    vis[id[S]] = 1, dis[id[S]] = 0;
    q.push (id[S]);
    for (; !q.empty (); ) {
        int u = q.front ();
        q.pop (), vis[u] = 0;
        for (register int i = 0; i < h[u].size(); i ++) {
            int v = h[u][i], w = hh[u][i];
            if (dis[v] < dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    q.push (v);
                    vis[v] = 1;
                }
            }
        }
    }
    for (register int i = 1; i <= P; i ++)
        ans = max (ans, dis[id[p[i]] + gg]);
    printf ("%d\n", ans);
}

void djj_lxy () {
    djj (), lxy ();
}

int main() {
    djj_lxy ();
}

/* 样例，本题样例还算不错了
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
*/

本题就完了，完结撒花~~

距离新 Noip 还有不到 2 个月的时间，祝大家 rp ++

也希望自己能更努力一些，加油！