【BZOJ1179】【APIO2009】抢掠计划

首先用Tarjan缩下点

那么就是一个有向无环图上的dp了。。我写的记忆化搜索

// <1179.cpp> - 07/28/16 20:25:25
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=1000010;
const int INF=1e9;
int bt,b[MAXN],next[MAXN],to[MAXN];
inline void add(int y,int x){next[++bt]=b[x];b[x]=bt;to[bt]=y;}
int tot,dfn[MAXN],low[MAXN],f[MAXN];
lol a[MAXN];
bool in[MAXN],ex[MAXN];
stack <int> st;
void dfs(int x){
    dfn[x]=low[x]=++tot;
    st.push(x);in[x]=1;
    for(int i=b[x];i;i=next[i])
        if(!dfn[to[i]]){
            dfs(to[i]);
            low[x]=min(low[x],low[to[i]]);
        }else if(in[to[i]])low[x]=min(low[x],dfn[to[i]]);
    if(dfn[x]==low[x]){
        for(int i=b[x];i;i=next[i])to[i]=f[to[i]];
        int sec;
        while(1){
            sec=st.top();st.pop();
            in[sec]=0;
            f[sec]=x;
            if(sec==x)break;
            a[x]+=a[sec];
            for(int i=b[sec];i;i=next[i]){
                if(f[to[i]]==x)continue;
                add(f[to[i]],x);
            }
        }
    }
}
lol ans[MAXN];
lol dfs2(int x){
    in[x]=1;
    lol get=0;
    for(int i=b[x];i;i=next[i]){
        if(!in[to[i]])ans[to[i]]=dfs2(to[i]);
        get=max(get,ans[to[i]]);
    }
    if(get)return get+a[x];
    return ex[x]*a[x];
}
int main(){
    int n=gi(),m=gi();
    for(int i=1;i<=m;i++)add(gi(),gi());
    for(int i=1;i<=n;i++)a[i]=gi();
    for(int i=n;i;i--)if(!dfn[i])dfs(i);
    int s=f[gi()],p=gi();
    for(int i=1;i<=p;i++)ex[f[gi()]]=1;
    printf("%lld",dfs2(s));
    return 0;
}

// <1179.cpp> - 07/28/16 20:25:25

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <stack>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=1000010;

const int INF=1e9;

int bt,b[MAXN],next[MAXN],to[MAXN];

inline void add(int y,int x){next[++bt]=b[x];b[x]=bt;to[bt]=y;}

int tot,dfn[MAXN],low[MAXN],f[MAXN];

lol a[MAXN];

bool in[MAXN],ex[MAXN];

stack <int> st;

void dfs(int x){

dfn[x]=low[x]=++tot;

st.push(x);in[x]=1;

for(int i=b[x];i;i=next[i])

if(!dfn[to[i]]){

dfs(to[i]);

low[x]=min(low[x],low[to[i]]);

}else if(in[to[i]])low[x]=min(low[x],dfn[to[i]]);

if(dfn[x]==low[x]){

for(int i=b[x];i;i=next[i])to[i]=f[to[i]];

int sec;

while(1){

sec=st.top();st.pop();

in[sec]=0;

f[sec]=x;

if(sec==x)break;

a[x]+=a[sec];

for(int i=b[sec];i;i=next[i]){

if(f[to[i]]==x)continue;

add(f[to[i]],x);

}

lol ans[MAXN];

lol dfs2(int x){

in[x]=1;

lol get=0;

for(int i=b[x];i;i=next[i]){

if(!in[to[i]])ans[to[i]]=dfs2(to[i]);

get=max(get,ans[to[i]]);

}

if(get)return get+a[x];

return ex[x]*a[x];

}

int main(){

int n=gi(),m=gi();

for(int i=1;i<=m;i++)add(gi(),gi());

for(int i=1;i<=n;i++)a[i]=gi();

for(int i=n;i;i--)if(!dfn[i])dfs(i);

int s=f[gi()],p=gi();

for(int i=1;i<=p;i++)ex[f[gi()]]=1;

printf("%lld",dfs2(s));

return 0;

}

说点什么