BZOJ1179 Atm //缩点＋spfa

1179: [Apio2009]Atm

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
15
1 4
4
3
5
6

Sample Output

HINT

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

分析：

这道题其实很迷。首先这道题发现如果在一个强连通分量里面，都可以走到，而且也没有限制走的次数，所以我们可以将在强连通分量里面的点，缩成一个全新的点。之后造出来一个全新的图。boom！新造出来的图可以走一遍最短路spfa。就好了。

至于怎么缩点。
用并查集先找到父亲与儿子。之后每次判断出一个强量通分量就用将他们的父亲全连成第一个数。
之后在新建图（如果一个点的父亲与儿子的父亲不相同，那他们1，连上2，建边）
这个边其实可以重复利用。这样可以节省空间。

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
struct node{
    int infont,v,next,val;
}edge[1000010];
int strack[1000010],cnt,father[1000000],heads[500010],d[500010],s,p;
int DFN[1000000],LOW[1000000],bar[1000000],visit[1000010],du[500010];
int n,m,index_1,head;
void address(int x,int y){
    edge[++cnt].infont=x;
    edge[cnt].v=y;
    edge[cnt].next=heads[x];
    heads[x]=cnt;
    return ;
}
void tarjan(int x){
    LOW[x]=DFN[x]=++index_1;
    visit[x]=1;
    strack[++head]=x;
    for(int i=heads[x];i!=-1;i=edge[i].next){
if(!DFN[edge[i].v]){
    tarjan(edge[i].v);
    LOW[x]=min(LOW[x],LOW[edge[i].v]);
}
else if(visit[edge[i].v]){
    LOW[x]=min(LOW[x],DFN[edge[i].v]);
}
    }
    if(LOW[x]==DFN[x])
    {
while(strack[head]!=x){
    visit[strack[head]]=0;
    d[x]+=d[strack[head]];
    father[strack[head]]=x;
    head--;
}
head--;
visit[x]=0;
    }
    return ;
}
void build(){
    memset(heads,-1,sizeof(heads));
    cnt=0;
    for(int i=1;i<=m;++i)
    {
if(father[edge[i].infont]!=father[edge[i].v])
    address(father[edge[i].infont],father[edge[i].v]);
    }
    return ;
}
void SPFA(int x)
{
    memset(visit,0,sizeof(visit));
    memset(strack,0,sizeof(strack));
    memset(du,-0x3f,sizeof(du));
    int last;
    last=head=1;
    strack[head]=x;
    visit[x]=1;
    du[x]=d[x];
    while(head<=last){
int news=strack[head];
for(int i=heads[news];i!=-1;i=edge[i].next)
{
    if(du[edge[i].v]<du[news]+d[edge[i].v])
    {
du[edge[i].v]=du[news]+d[edge[i].v];
if(visit[edge[i].v])continue;
visit[edge[i].v]=1;
strack[++last]=edge[i].v;
    }
}
head++;
visit[news]=0;
    }
    return ;
}
int main( ){
    memset(heads,-1,sizeof(heads));
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=1;i<=m;++i){
scanf("%d%d",&a,&b);
address(a,b);
    }
    for(int i=1;i<=n;++i){
scanf("%d",&a);
d[i]=a;
father[i]=i;
    }
    for(int i=1;i<=n;++i)if(!DFN[i])tarjan(i);
    build();
    scanf("%d%d",&a,&b);
    SPFA(father[a]);
    int ans=0;
    for(int i=1;i<=b;++i)
    {
scanf("%d",&a);
ans=max(ans,du[father[a]]);
    }
    printf("%d",ans);
    return 0;
}