首页 > 代码库 > BZOJ 1179 Atm 题解
BZOJ 1179 Atm 题解
BZOJ 1179 Atm 题解
SPFA Algorithm
Tarjan Algorithm
Description
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
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的单向的道路到达其中的至少一个酒吧。
————————————————————————————分割线————————————————————————————
思路：
先用Tarjan算法求出途中的所有强连通分量，再讲每个分量值加和为点，再用SPFA算法求出以S为源点，最大价值的路径。
代码如下,(不是我的代码)
1 //Code By にしきのまき 2 3 #include<stdio.h> 4 #include<algorithm> 5 #include<string.h> 6 using namespace std; 7 struct node 8 { 9 int v; 10 int next; 11 }; 12 int n,m; 13 node e[500010],map[500010];//邻接表存图 14 int st[500010],head[500010],cnt; 15 int atm[500010],money[500010]; 16 int d[500010],q[500010];//最短路径＆SPFA要用的队列 17 void build(int a,int b) 18 { 19 e[++cnt].v=b; 20 e[cnt].next=st[a]; 21 st[a]=cnt; 22 }//建图找强连通分量 23 int stack[500010],top;//tarjan需要的栈 24 int dfn[500010],low[500010],dex;//时间戳（深搜序）、可回溯到的最早栈中时间戳、次序编号 25 bool vis[500010];//tarjan时判断点是否在栈中，SPFA时判断点是否在队列中 26 int color[500010],num;//表示同一强连通分量上的点 27 void tarjan(int x)//tarjan找强连通分量 28 { 29 dfn[x]=++dex; 30 low[x]=dex; 31 vis[x]=true; 32 stack[++top]=x;//当前点入栈 33 int i; 34 for(i=st[x];i!=0;i=e[i].next)//枚举以当前点为起点的边 35 { 36 int temp=e[i].v;//temp为当前被枚举边的终点 37 if(!dfn[temp])//如果当前边终点未被处理 38 { 39 tarjan(temp); 40 low[x]=min(low[x],low[temp]); 41 } 42 else if(vis[temp])low[x]=min(low[x],dfn[temp]); 43 } 44 if(dfn[x]==low[x]) 45 { 46 vis[x]=false; 47 color[x]=++num;//标记当前强连通分量内的点 48 while(stack[top]!=x)//栈顶元素依次出栈 49 { 50 color[stack[top]]=num; 51 vis[stack[top--]]=false; 52 } 53 top--; 54 } 55 } 56 void add()// 把同一强连通分量上的点缩成一个点，把这些点连成一张新图 57 { 58 cnt=0; 59 int i,j; 60 for(i=1;i<=n;i++) 61 { 62 for(j=st[i];j!=0;j=e[j].next) 63 { 64 int temp=e[j].v; 65 if(color[i]!=color[temp]) 66 { 67 map[++cnt].v=color[temp]; 68 map[cnt].next=head[color[i]]; 69 head[color[i]]=cnt; 70 } 71 } 72 73 } 74 } 75 void spfa(int x)//SPFA找最长路 76 { 77 memset(vis,false,sizeof(vis)); 78 int l=1,r=1; 79 q[l]=x;//初始点放入队列 80 vis[x]=true; 81 d[x]=money[x]; 82 while(l<=r) 83 { 84 int u=q[l++]; 85 for(int i=head[u];i!=0;i=map[i].next)//遍历所有以当前点为起点的边 86 { 87 int v=map[i].v; 88 if(d[v]<d[u]+money[v]) 89 { 90 d[v]=d[u]+money[v]; 91 if(vis[v])continue; 92 q[++r]=v;//如果当前拓展的边的终点不在队列里，就把它放入队尾 93 vis[v]=true; 94 } 95 } 96 vis[u]=false; 97 } 98 } 99 int main()100 {101 int a,b,i,s,p,o,ans=0;102 scanf("%d%d",&n,&m);103 for(i=1;i<=m;i++)104 {105 scanf("%d%d",&a,&b);106 build(a,b);107 }//建初始图 108 for(i=1;i<=n;i++)109 {110 if(!dfn[i])tarjan(i);//找强连通分量111 }112 add();//建新图 113 for(i=1;i<=n;i++)114 {115 scanf("%d",&atm[i]);116 money[color[i]]+=atm[i];117 }118 scanf("%d%d",&s,&p);119 spfa(color[s]);//找单源最短路 120 for(i=1;i<=p;i++)121 {122 scanf("%d",&o);123 ans=max(ans,d[color[o]]);//找到以酒吧为终点的最长路 124 }125 printf("%d",ans);126 return 0;127 }
2016-09-14 20:00:54
(完)
BZOJ 1179 Atm 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。