首页 > 代码库 > bzoj 1179 Atm
bzoj 1179 Atm
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1179
题解:
一道比较综合的图论题
直接讲正解:
如果这个图G中存在某个强连通分量,那么这个强连通分量中的所有ATM即可视为都被抢到,所有的酒吧都可视为重点,并且也可以从这个强连通分量的任何结点出发继续向外扩展
如果这个图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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。