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
1

5
1 4
4
3
5
6

Sample Output

47

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;
}