BZOJ 1179: [APIO2009]ATM – [Tarjan/最长路]


题目传送门(BZOJ)
>原文链接<

题解 :

一个环里的提款机, 如果抢了一个就可以全抢, 这是显而易见的

所以我们先用Tarjan缩点, SCC点权是其包含的所有点的点权和.

求一次以1为原点的最长路.

从所有输入的酒吧里, 挑一个距离最大的为答案即可

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 510000;
int head[N], to[N], nxt[N]; int v[N]; int dfn[N], low[N], pos[N]; int place[N]; int fr[N], ed[N]; int idx, tot; stacks; int ins[N]; int a[N], cnt; int f[N]; int S; int P;
void add(int x, int y) {
    to[++cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
}
void Tarjan(int p) {
    dfn[p] = low[p] = ++idx;
    ins[p] = 1;
    s.push(p);       
    for(int i=head[p];i;i=nxt[i]) {
        if(!dfn[to[i]]) {
            Tarjan(to[i]);
            low[p] = min(low[p], low[to[i]]);
        }
        else if(ins[to[i]]) {
            low[p] = min(low[p], dfn[to[i]]);
        }
    }
    if(low[p] == dfn[p]) {
        int t = 0;
        tot++;
        while(t!=p) {
            t = s.top();s.pop();
            ins[t] = 0;
            place[t] = tot;
            v[tot]+=a[t];
        }
    }
}
int inq[N];
void spfa() {
    queueq;
    q.push(place[S]);
    f[place[S]] = v[place[S]];
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for(int i = head[u];i;i=nxt[i]) {
            if(f[to[i]]

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注