刷题向》图论》BZOJ1179 关于tarjan和SPFA的15秒(normal)

　　这道题可以考察图论的掌握程度（算半道水题）

　　题目如下

输入

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

输出

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

样例输入

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

样例输出

提示

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

题解

这道题考到了spfa和tarjan唯一需要考虑的地方是，当你tarjan一遍之后，你需要做缩点，那么缩点之后你要做的事是重建整张图，把同一强连通分量里的点缩到同一点，再次建边，然后就是裸SPFA的事情了(缩点的过程用并查集考虑)

下面贴出代码

 #include<cstdio>

 #include<cstring>

 struct shit{

     int aim;

     int next;

     int get;

     bool use;

 }e[];

 int max(int x,int y)

 {

     return x>y?x:y;

 }

 int min(int x,int y)

 {

     return x<y?x:y;

 }

 int point,head[],n,m,ass,cnt,stack[],low[],time[],a,b,T;

 int father[],quq[],val[],d[],star,ans;

 bool f[];

 void fuck(int x,int y)

 {

     e[++point].aim=y;

     e[point].get=x;

     e[point].next=head[x];

     head[x]=point;

 }

 void rebuild()

 {

     memset(head,,sizeof(head));

     point=;

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

         if(father[e[i].get]==father[e[i].aim]);

         else fuck(father[e[i].get],father[e[i].aim]);

 }

 void tarjan(int sb)

 {

     low[sb]=time[sb]=++T;

     f[sb]=true;

     stack[++ass]=sb;

     for(int k=head[sb];k!=;k=e[k].next)

     {

         if(!time[e[k].aim])

         {

             tarjan(e[k].aim);

             low[sb]=min(low[sb],low[e[k].aim]);

         }

         else if(f[e[k].aim])low[sb]=min(low[sb],time[e[k].aim]);

     }

     if(time[sb]==low[sb])

     {

         f[sb]=false;

         while(stack[ass]!=sb)

         {

             val[sb]+=val[stack[ass]];

             f[stack[ass]]=false;

             father[stack[ass--]]=sb;

         }

         ass--;

     }

 }

 void SPFA(int num)

 {

     memset(f,,sizeof(f));

     star=,ass=;

     quq[++star]=num,f[num]=true,d[num]=val[num];

     while(star<=ass)

     {

         int u=quq[star++];

         for(int k=head[u];k!=;k=e[k].next)

         {

             int v=e[k].aim;

             if(d[u]+val[v]>d[v])

             {

                 d[v]=d[u]+val[v];

                 if(f[v])continue;

                     quq[++ass]=v;

                     f[v]=true;

             }

         }

         f[u]=false;

     }

     return ;

 }

 int main()

 {

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

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

     {

         scanf("%d%d",&a,&b);

         fuck(a,b);

     }

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

     {

         father[i]=i;

         scanf("%d",&val[i]);

     }

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

     rebuild();

     scanf("%d%d",&a,&b);

     SPFA(father[a]);

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

     {

         scanf("%d",&a);

         ans=max(ans,d[father[a]]);

     }

     printf("%d",ans);

     return ;

 }

巴特西

刷题向》图论》BZOJ1179 关于tarjan和SPFA的15秒(normal)

最新文章

热门文章