BZOJ 1179: [Apio2009]Atm

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解
代码

Description

Input

第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号

Output

输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

Sample Input

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

Sample Output

HINT

50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

题解

我们可以先Tarjan缩点，然后SPFA就能跑过！
注意中心城市在S号，而不是1号。【← ←这样我Wa过一次
注意对于100%的数据N, M<=500000【我一眼看到了3000和500000，还以为N<=3000,M<=500000，结果有Re一次、我没救了

代码

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int Maxn=500010;
const int Maxm=500010;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int a,int b){
        v=a;nxt=b;
    }
};
Edge e[Maxm];
int head[Maxn];
int nhead[Maxn];
int val[Maxn];
int nume;
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
}
inline void reEdge(int u,int v){
    e[++nume]=Edge(v,nhead[u]);
    nhead[u]=nume;
}
int dfn[Maxn],low[Maxn];
int ind;
bool inque[Maxn],vis[Maxn];
int bel[Maxn];
int scc;
int stack[Maxn];
int top;
int sVal[Maxn];
inline int remax(int a,int b){
    if (a>b) return a;
    return b;
}
inline int remin(int a,int b){
    if (a<b) return a;
    return b;
}
void tarjan(int x){
    vis[x]=inque[x]=true;
    low[x]=dfn[x]=++ind;
    stack[++top]=x;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (!vis[v]){
            tarjan(v);
            low[x]=remin(low[x],low[v]);
        }else if (inque[v]){
            low[x]=remin(low[x],dfn[v]);
        }
    }
    if (low[x]==dfn[x]){
        scc++;
        int now=0;
        while(now!=x){
            now=stack[top--];
            sVal[scc]+=val[now];
            bel[now]=scc;
            inque[now]=false;
        }
    }
}
int n,m;
int S,P;
int p[Maxn];
inline void rebuild(){
    int nume=0;
    for (int k=1;k<=n;k++){
        for (int i=head[k];i;i=e[i].nxt)
            if (bel[k]!=bel[e[i].v]) reEdge(bel[k],bel[e[i].v]);
    }
}
int dist[Maxn];
queue<int> que;
inline void spfa(){
    while(!que.empty()) que.pop();
    memset(inque,false,sizeof(inque));
    que.push(bel[S]);
    dist[bel[S]]=sVal[bel[S]];
    inque[bel[S]]=true;
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for (int i=nhead[now];i;i=e[i].nxt){
            int v=e[i].v;
            if (dist[v]<dist[now]+sVal[v]){
                dist[v]=dist[now]+sVal[v];
                if (!inque[v]){
                    inque[v]=true;
                    que.push(v);
                }
            }
        }
        inque[now]=false;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addEdge(x,y);
    }
    for (int i=1;i<=n;i++) scanf("%d",&val[i]);
    scanf("%d%d",&S,&P);
    for (int i=1;i<=P;i++) scanf("%d",&p[i]);
    for (int i=1;i<=n;i++) if (!vis[i]) tarjan(i);
    rebuild();
    spfa();
    int Ans=0;
    for (int i=1;i<=P;i++) Ans=remax(Ans,dist[bel[p[i]]]);
    printf("%dn",Ans);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int Maxn=500010;

const int Maxm=500010;

struct Edge{

int v,nxt;

Edge(){}

Edge(int a,int b){

v=a;nxt=b;

}

};

Edge e[Maxm];

int head[Maxn];

int nhead[Maxn];

int val[Maxn];

int nume;

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

}

inline void reEdge(int u,int v){

e[++nume]=Edge(v,nhead[u]);

nhead[u]=nume;

}

int dfn[Maxn],low[Maxn];

int ind;

bool inque[Maxn],vis[Maxn];

int bel[Maxn];

int scc;

int stack[Maxn];

int top;

int sVal[Maxn];

inline int remax(int a,int b){

if (a>b) return a;

return b;

}

inline int remin(int a,int b){

if (a<b) return a;

return b;

}

void tarjan(int x){

vis[x]=inque[x]=true;

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

stack[++top]=x;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (!vis[v]){

tarjan(v);

low[x]=remin(low[x],low[v]);

}else if (inque[v]){

low[x]=remin(low[x],dfn[v]);

}

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

scc++;

int now=0;

while(now!=x){

now=stack[top--];

sVal[scc]+=val[now];

bel[now]=scc;

inque[now]=false;

}

int n,m;

int S,P;

int p[Maxn];

inline void rebuild(){

int nume=0;

for (int k=1;k<=n;k++){

for (int i=head[k];i;i=e[i].nxt)

if (bel[k]!=bel[e[i].v]) reEdge(bel[k],bel[e[i].v]);

}

int dist[Maxn];

queue<int> que;

inline void spfa(){

while(!que.empty()) que.pop();

memset(inque,false,sizeof(inque));

que.push(bel[S]);

dist[bel[S]]=sVal[bel[S]];

inque[bel[S]]=true;

while(!que.empty()){

int now=que.front();

que.pop();

for (int i=nhead[now];i;i=e[i].nxt){

int v=e[i].v;

if (dist[v]<dist[now]+sVal[v]){

dist[v]=dist[now]+sVal[v];

if (!inque[v]){

inque[v]=true;

que.push(v);

}

inque[now]=false;

}

int main(){

scanf("%d%d",&n,&m);

for (int i=1;i<=m;i++){

int x,y;

scanf("%d%d",&x,&y);

addEdge(x,y);

}

for (int i=1;i<=n;i++) scanf("%d",&val[i]);

scanf("%d%d",&S,&P);

for (int i=1;i<=P;i++) scanf("%d",&p[i]);

for (int i=1;i<=n;i++) if (!vis[i]) tarjan(i);

rebuild();

spfa();

int Ans=0;

for (int i=1;i<=P;i++) Ans=remax(Ans,dist[bel[p[i]]]);

printf("%dn",Ans);

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑