首页 > 代码库 > bzoj1179（Atm）
bzoj1179（Atm）
---恢复内容开始---
1179: [Apio2009]Atm
Time Limit: 15 Sec Memory Limit: 162 MBDescription
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的单向的道路到达其中的至少一个酒吧。
这道题写了好久，终于写出来啦（哭。。。。。）
这道题思路大概是这样的，用adjacency list存完边后，先做一个tarjan并染色的预处理，然后把所有相同颜色的城市看成一个强连通分量，把这个强连通分量的颜色设置为新的地图编号为color的一个城市，然后将记录下来的原先的城市的道路，一一判断是否在新的map中是一座城市，若不是，那重新建立道路。（当然也得重新设置酒吧的位置）
最后跑一遍spfa求出每个酒吧的最大值即可（因为把强连通分量看成了一个城市了，所以不会再产生环）。
还是一样，贴代码（其实后来发现有一点可以省略不写的，就是重新设置好城市以后，把酒吧原来所在城市的的编号改成现在的就行，，还多开了一个array）
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 const int maxn=500005; 5 using namespace std; 6 struct node {int next,aim;}; 7 node f[maxn],e[maxn]; 8 int point,head[maxn],Low[maxn],stack[maxn],DFN[maxn],dep,top,cl[maxn],color,queue[maxn],n,m,newmoney[maxn]; 9 bool vis[maxn],bar[maxn],newbar[maxn]; 10 int x1[maxn],y1[maxn],money[maxn],start,t; 11 long long ans,d[maxn]; 12 void add(node *array,int x,int y) 13 { 14 point++; 15 array[point].next=head[x]; 16 head[x]=point; 17 array[point].aim=y; 18 } 19 void tarjan(int x) 20 { 21 DFN[x]=Low[x]=++dep;//为节点u设定次序编号和Low初值 22 stack[++top]=x; 23 vis[x]=true; //将节点u压入栈中 24 for (int i=head[x];i!=0;i=e[i].next)//枚举每一条边 25 if (!DFN[e[i].aim]) 26 {//如果节点v未被访问过 27 tarjan(e[i].aim);//继续向下找 28 Low[x]=min(Low[x],Low[e[i].aim]); 29 } 30 else if (vis[e[i].aim])//如果节点v还在栈内 31 Low[x]=min(Low[x],DFN[e[i].aim]); 32 if (DFN[x]==Low[x])//如果节点u是强连通分量的根 33 { 34 vis[x]=false;if(cl[x]==0)cl[x]=++color; 35 while(stack[top]!=x) 36 { 37 cl[stack[top]]=color; 38 vis[stack[top]]=false; 39 top--; 40 } 41 top--; 42 } 43 44 } 45 void spfa(int x) 46 { 47 int Head=1,tail=2; 48 queue[Head]=x; 49 while(Head<tail) 50 { 51 for(int i=head[queue[Head]];i!=0;i=f[i].next) 52 { 53 int u=f[i].aim; 54 if(d[queue[Head]]+newmoney[u]>d[u]) 55 { 56 d[u]=d[queue[Head]]+newmoney[u]; 57 if(!vis[u])queue[tail++]=u; 58 vis[u]=true; 59 } 60 } 61 vis[queue[Head]]=false; 62 Head++; 63 } 64 } 65 int main() 66 { 67 scanf("%d%d",&n,&m); 68 for(int i=1;i<=m;i++) 69 { 70 scanf("%d%d",&x1[i],&y1[i]); 71 add(e,x1[i],y1[i]); 72 } 73 for(int i=1;i<=n;i++) 74 { 75 scanf("%d",&money[i]); 76 } 77 scanf("%d",&start); 78 scanf("%d",&t); 79 for(int i=1;i<=t;i++) 80 { 81 int l; 82 scanf("%d",&l); 83 bar[l]=true; 84 } 85 for(int i=1;i<=n;i++) 86 if(!DFN[i])tarjan(i); 87 memset(head,0,sizeof(head)); 88 point=0; 89 for(int i=1;i<=m;i++) 90 { 91 int p=cl[x1[i]],q=cl[y1[i]]; 92 if(p!=q)add(f,p,q); 93 } 94 for(int i=1;i<=n;i++) 95 newmoney[cl[i]]+=money[i]; 96 start=cl[start]; 97 for(int i=1;i<=n;i++) 98 { 99 if(bar[i]){100 newbar[cl[i]]=true;101 }102 }103 memset(vis,0,sizeof(vis));104 d[start]=newmoney[start];105 vis[start]=true;106 spfa(start);107 for(int i=1;i<=color;i++)108 if(newbar[i])ans=max(ans,d[i]);109 printf("%lld",ans);110 return 0;111 }
---恢复内容结束---
bzoj1179（Atm）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。