0%

[APIO2009]抢掠计划

发表于 更新于 分类于

#题目链接

P3627 抢掠计划

#题意简述

给定一张有向图，1个起点与若干个终点，每个点可经过若干次。使到达图中的某一个终点的路径中，所经过的点的权值总和最大。求出这个最大的权值总和。

#简要做法

缩点模板题。用$Tarjan$缩点，然后在缩点图上用$SPFA$跑一遍最长路，便可得到答案。

#参考代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 5e5 + 5;
int n , m , s , l;
int head[maxn] , te , head1[maxn] , te1;
struct edge {
    int to , next , val;
}e[maxn] , e1[maxn];
int w[maxn];
int low[maxn] , dfn[maxn] , belong[maxn] , cnt;
inline void addE(int u , int v) {
    e[++te].to = v;
    e[te].next = head[u];
    head[u] = te;
}
inline void add1(int u , int v , int w) {
    e1[++te1].to = v;
    e1[te1].next = head1[u];
    head1[u] = te1;
    e1[te1].val = w;
} 
stack <int> st;
bool vis[maxn];
void tarjan(int x) {
    vis[x] = true;
    st.push(x);
    low[x] = dfn[x] = ++cnt;
    for(register int i = head[x]; i; i = e[i].next) {
        int to = e[i].to;
        if(!dfn[to]) {
            tarjan(to);
            low[x] = min(low[x] , low[to]);
        }
        if(vis[to])
            low[x] = min(low[x] , dfn[to]);
    }
    if(low[x] == dfn[x]) {
        int t;
        do {
            t = st.top();
            vis[t] = false;
            st.pop();
            belong[t] = x;
            if(x != t) w[x] += w[t];
        }while(t != x);
    }
}
queue <int> q;
int dis[maxn];
void spfa() {
    dis[belong[s]] = w[belong[s]];
    q.push(belong[s]);
    vis[belong[s]] = true;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        vis[cur] = false;
        for(register int i = head1[cur]; i; i = e1[i].next) {
            int to = e1[i].to;
            if(dis[to] < dis[cur] + e1[i].val) {
                dis[to] = dis[cur] + e1[i].val;
                if(!vis[to])
                    q.push(to);
                vis[to] = true;
            }
        }
    }
}
int main() {
    scanf("%d%d" , &n , &m);
    for(register int i = 1; i <= m; ++i) {
        int u , v;
        scanf("%d%d" , &u , &v);
        addE(u , v);
    }
    for(register int i = 1; i <= n; ++i)
        scanf("%d" , &w[i]);
    scanf("%d%d" , &s , &l);
    for(register int i = 1; i <= n; ++i)
        if(!dfn[i])	tarjan(i);
    for(register int i = 1; i <= n; ++i) {
        int u = belong[i];
        for(register int j = head[i]; j; j = e[j].next) {
            int v = belong[e[j].to];
            if(u != v)
                add1(u , v , w[v]);
        }
    }
    spfa();
    int bar , ans = 0;
    for(register int i = 1; i <= l; ++i) {
        scanf("%d" , &bar);
        ans = max(ans , dis[belong[bar]]);
    }
    printf("%d\n" , ans);
    return 0;
}

基本上就这样啦！