【BZOJ1179】 [Apio2009]Atm tarjan缩点+SPFA

时间：2024-01-02 10:13:02

Description

【BZOJ1179】 [Apio2009]Atm tarjan缩点+SPFA

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的单向的道路到达其中的至少一个酒吧。

Source

1A大法爽，由于没有时间的限制，但又因为抢过的ATM没钱了，所以可以tarjan求还然后缩点，再SPFA加了点读入优化，发现慢的1B，WHY？，好像这道T可以DP啊。。。太弱了我。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <queue>

 #include <stack>

 #define N 500500

 #define M 500500

 using namespace std;

 struct data{int next,p;}e1[M],e2[M];

 int head1[N],head2[N],belong[N],low[N],dfn[N],mon[N],vscc[N],dis[N],inq[N],vis[N];

 int q1[N],q[N];

 int n,m,S,p,cnt,ans,qt,scc;

 inline int max(int x,int y){return x>y?x:y;}

 inline int min(int x,int y){return x<y?x:y;}

 inline int read()

 {

     char c;

     int anss=;

     while ((c=getchar())==' ' || c=='\n' || c=='\r');

     anss=c-'';

     while (isdigit(c=getchar())) anss=anss*+c-'';

     return anss;

 }

 void se1(int x,int y){cnt++; e1[cnt].next=head1[x]; head1[x]=cnt; e1[cnt].p=y;}

 void se2(int x,int y){cnt++; e2[cnt].next=head2[x]; head2[x]=cnt; e2[cnt].p=y;}

 void tarjan(int x)

 {

     vis[x]=inq[x]=;

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

     q1[++qt]=x;

     for (int i=head1[x];i;i=e1[i].next)

     {

         if (!vis[e1[i].p])

         {

             tarjan(e1[i].p);

             low[x]=min(low[x],low[e1[i].p]);

         }

         else if (inq[e1[i].p])    low[x]=min(low[x],low[e1[i].p]);

     }

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

     {

         int now=;

         scc++;

         while (now!=x)

         {

             now=q1[qt];qt--;

             belong[now]=scc;

             inq[now]=;

             vscc[scc]+=mon[now];

         }

     }

 }

 void part1_tarjan()

 {

     cnt=;

     for (int i=;i<=n;i++)

         if (!vis[i])    tarjan(i);

 }

 void part2_shr_point()

 {

     cnt=;

     for (int i=;i<=n;i++)

         for (int j=head1[i];j;j=e1[j].next)

             if (belong[i]!=belong[e1[j].p])

                 se2(belong[i],belong[e1[j].p]);

 }

 void part3_spfa()

 {

     memset(inq,,sizeof(inq));

     int t=,w=;

     q[t]=belong[S];

     inq[belong[S]]=;

     dis[belong[S]]=vscc[belong[S]];

     while  (t!=w)

     {

         int now=q[t];t++;

         for (int i=head2[now];i;i=e2[i].next)

             if (dis[e2[i].p]<dis[now]+vscc[e2[i].p])

             {

                 dis[e2[i].p]=dis[now]+vscc[e2[i].p];

                 if (!inq[e2[i].p])

                 {

                     inq[e2[i].p]=;

                     q[w++]=e2[i].p;

                 }

             }

         inq[now]=;

     }

 }

 int main()

 {

     n=read();m=read();

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

     {

         int x,y;

         x=read();y=read();

         se1(x,y);

     }

     for (int i=;i<=n;i++)    mon[i]=read();

     part1_tarjan();

     part2_shr_point();

     S=read();p=read();

     part3_spfa();

     for (int i=;i<=p;i++)

     {

         int x=read();

         if (dis[belong[x]]>ans) ans=dis[belong[x]];

     }

     printf("%d\n",ans);

     return ;

 }

相关文章