首页 > 代码库 > bzoj 1179 Atm

bzoj 1179 Atm

2024-08-16 19:33:31   221人阅读

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1179

题解：

　　一道比较综合的图论题
　　直接讲正解：
　　如果这个图G中存在某个强连通分量，那么这个强连通分量中的所有ATM即可视为都被抢到，所有的酒吧都可视为重点，并且也可以从这个强连通分量的任何结点出发继续向外扩展
　　所以先做一遍Tarjan，找出强连通分量，然后重新构图，把每个强连通分量缩成一个点，此点的权值即为原先强连通分量里所有点权之和，判断此点中有没有酒吧，再将原先所有连接强连通分量的边连接在这个点
　　最后做SPFA，找出权值最大的路径
　　这道题时间限制15s，空间162MB，所以一般不会TLE或MLE
  1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 using namespace std;  5 #define MAXN 500010  6 #define MAXM 500010  7 int n,m,time,cnt,head1[MAXN],DFN[MAXN],Low[MAXN],stack[MAXN],top,a1[MAXN],belong[MAXN];  8 bool vis[MAXN],bar1[MAXN];  9 struct node1 10 { 11     int v,next; 12 }edge1[MAXM]; 13 //以上变量基本是在进行tarjan（及之前）使用  14 int heads[MAXN],mm,a2[MAXN],s,p,d[MAXN],q[MAXN],head,tail,ans; 15 bool viss[MAXN]; 16 struct node2 17 { 18     int v,next; 19 }edge2[MAXM]; 20 //以上变量是在进行SPFA时使用  21 //a存放点权，bar记录是否有酒吧  22 bool bar2[MAXN]; 23 void add(int x,int y) 24 { 25     edge1[++cnt].next=head1[x]; 26     head1[x]=cnt; 27     edge1[cnt].v=y; 28 } 29 void buildmap(int k)//重新建图、连边  30 { 31     for(int i=1;i<=n;i++) 32     { 33         if(belong[i]==k) 34         { 35             for(int j=head1[i];j;j=edge1[j].next) 36             { 37                 if(belong[edge1[j].v]==k)continue; 38                 edge2[++m].next=heads[k]; 39                 heads[k]=m; 40                 edge2[m].v=belong[edge1[j].v]; 41             } 42         } 43     } 44 } 45 void tarjan(int u) 46 { 47     DFN[u]=Low[u]=++time; 48     vis[u]=true; 49     stack[++top]=u; 50     for(int i=head1[u];i;i=edge1[i].next) 51     { 52         int v=edge1[i].v;     53         if(!DFN[v])  54         { 55             tarjan(v); 56             Low[u]=min(Low[u],Low[v]); 57         } 58         else if(vis[v])Low[u]=min(Low[u],DFN[v]); 59     } 60     if(DFN[u]==Low[u])  61     { 62         int i; 63         cnt++; 64         do 65         { 66             i=stack[top--]; 67             vis[i]=false; 68             belong[i]=cnt; 69             a2[cnt]+=a1[i]; 70             if(bar1[i])bar2[cnt]=true;//先更新点权和是否有酒吧  71         }while(u!=i); 72     } 73 } 74 void SPFA() 75 { 76     head=1;tail=2; 77     q[1]=s; 78     viss[s]=1; 79     while(head<tail) 80     { 81         for(int i=heads[q[head]];i!=0;i=edge2[i].next) 82         { 83             if(d[q[head]]+a2[edge2[i].v]>d[edge2[i].v])//注意，这里不是边权，是点权  84             { 85                 d[edge2[i].v]=d[q[head]]+a2[edge2[i].v]; 86                 if(!viss[edge2[i].v]) 87                 { 88                     q[tail++]=edge2[i].v; 89                     viss[edge2[i].v]=true; 90                 } 91             } 92         } 93         viss[q[head]]=false; 94         head++; 95     } 96 } 97 int main() 98 { 99     scanf("%d%d",&n,&m);100     for(int i=1;i<=m;i++)101     {102         int x,y;103         scanf("%d%d",&x,&y);104         add(x,y);105     }106     for(int i=1;i<=n;i++)107     {108         scanf("%d",&a1[i]);109     }110     scanf("%d%d",&s,&p);111     for(int i=1;i<=p;i++)112     {113         int x;114         scanf("%d",&x);115         bar1[x]=true;116     }117     cnt=0;118     m=0;119     for(int i=1;i<=n;i++)120         if(!DFN[i])tarjan(i);121     for(int i=1;i<=cnt;i++)122         buildmap(i);123     s=belong[s];124     for(int i=1;i<=cnt;i++)125     {126         d[i]=a2[i];127     }128     SPFA();129     for(int i=1;i<=cnt;i++)130     {131         if(bar2[i])ans=max(ans,d[i]);132     }133     printf("%d",ans);134     return 0;135 }

 

bzoj 1179 Atm


联系
我们