M_sea

洛谷3627 [APIO2009]抢掠计划
Luogu分析震惊!某蒟蒻因数组开小而反复TLE!显然强连通分量内的点可以互相到达。那么就缩点,然后跑个最长路即可...
扫描右侧二维码阅读全文
28
2018/10

洛谷3627 [APIO2009]抢掠计划

Luogu

分析

震惊!某蒟蒻因数组开小而反复TLE!

显然强连通分量内的点可以互相到达。

那么就缩点,然后跑个最长路即可。

注意权值是点权。

细节很多,见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge { int v,nxt; };
Edge e[500010];
int head[500010],cnt=0;
int x[500010],y[500010];

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u],head[u]=cnt;
}

int n,m,s,p,new_s;
int dfn[500010],low[500010];
int sta[500010],top=0;
int instack[500010];
int dfs_clock=0;
int belong[500010],sum[500010];
int tot=0;
int val[500010];
int isbar[500010],havebar[500010];

inline void Tarjan(int u) {
    dfn[u]=low[u]=++dfs_clock;
    sta[++top]=u; instack[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (instack[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) {
        ++tot; int now;
        while (233) {
            instack[now=sta[top--]]=0;
            belong[now]=tot,sum[tot]+=val[now];
            if (isbar[now]) havebar[tot]=1;
            if (now==s) new_s=tot;
            if (now==u) break;
        }
    }
}

int dis[500010],inq[500010];

inline void SPFA(int s) {
    queue<int> Q;
    memset(dis,-1,sizeof(dis));
    dis[s]=sum[s],inq[s]=1; Q.push(s);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=sum[v];
            if (dis[u]+w>dis[v]) {
                dis[v]=dis[u]+w;
                if (!inq[v]) {
                    Q.push(v);
                    inq[v]=1;
                }
            }
        }
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;i++) {
        x[i]=read(),y[i]=read();
        addEdge(x[i],y[i]);
    }
    for (re int i=1;i<=n;i++) val[i]=read();
    s=read(),p=read();
    for (re int i=1;i<=p;i++) isbar[read()]=1;
    Tarjan(s);
    cnt=0; memset(head,0,sizeof(head));
    for (re int i=1;i<=m;i++) {
        int u=x[i],v=y[i];
        if (belong[u]!=belong[v])
            addEdge(belong[u],belong[v]);
    }
    SPFA(new_s);
    int ans=0;
    for (re int i=1;i<=tot;i++)
        if (havebar[i]) ans=max(ans,dis[i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 02 PM

发表评论

4 条评论

  1. ZCDHJ

    DAG上最长路可以dp跑

    1. M_sea
      @ZCDHJ

      我知道啊qwq

  2. smy

    不是DAG的dp吗qwq

    1. M_sea
      @smy

      SPFA最长路吼啊qwq