首页 > 代码库 > BZOJ1179: [Apio2009]Atm
BZOJ1179: [Apio2009]Atm
1179: [Apio2009]Atm
Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 1427 Solved: 544
[Submit][Status]
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
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
题解：
tarjan之后以scc[s]为起点做一遍spfa即可，若该scc内有酒吧则用它的d值更新答案
重构图的一种比较好的方法就是把所有的边记下来，tarjan之后可以memset（head,0,sizeof(head))，tot=0，重新insert
就不用在开其他的数组了，具体看代码
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 500000+1000013 #define maxm 500+10014 #define eps 1e-1015 #define ll long long16 using namespace std;17 inline int read()18 {19 int x=0,f=1;char ch=getchar();20 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}21 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}22 return x*f;23 }24 int n,m,ss,p,cnt,tot,ti,top,head[maxn],low[maxn],dfn[maxn],scc[maxn];25 int sta[maxn],from[maxn],go[maxn],q[2*maxn],a[maxn];26 ll ans,s[maxn],d[maxn];27 bool b[maxn],c[maxn],v[maxn];28 29 struct edge{int go,next;}e[maxn];30 void insert(int x,int y)31 {32 e[++tot].go=y;e[tot].next=head[x];head[x]=tot;33 }34 void dfs(int x)35 {36 int y;37 low[x]=dfn[x]=++ti;sta[++top]=x;38 for(int i=head[x];i;i=e[i].next)39 if (!dfn[y=e[i].go])40 {41 dfs(y);42 low[x]=min(low[x],low[y]);43 }44 else if(!scc[y])low[x]=min(low[x],dfn[y]);45 if(low[x]==dfn[x])46 {47 cnt++;48 while(1)49 {50 scc[y=sta[top--]]=cnt;s[cnt]+=a[y];51 if(b[y])c[cnt]=1;52 if(y==x)break;53 }54 } 55 }56 void tarjan()57 {58 for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);59 }60 void spfa()61 {62 for(int i=1;i<=cnt;++i) d[i]=0;63 memset(v,0,sizeof(v));64 int l=0,r=1,x,y;q[1]=scc[ss];d[scc[ss]]=s[scc[ss]];65 while(l!=r)66 {67 x=q[++l];if(l==maxn)l=0;v[x]=0;68 for(int i=head[x];i;i=e[i].next)69 if(d[x]+s[y=e[i].go]>d[y])70 {71 d[y]=d[x]+s[y];72 if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;}73 }74 }75 }76 int main()77 {78 freopen("input.txt","r",stdin);79 freopen("output.txt","w",stdout);80 n=read();m=read();81 int x,y;82 for(int i=1;i<=m;i++)from[i]=read(),go[i]=read(),insert(from[i],go[i]);83 for(int i=1;i<=n;i++)a[i]=read();84 ss=read();p=read();85 for(int i=1;i<=p;i++)x=read(),b[x]=1;86 tarjan();87 memset(head,0,sizeof(head));tot=0;88 for(int i=1;i<=m;i++)89 if(scc[x=from[i]]!=scc[y=go[i]])90 {91 insert(scc[x],scc[y]);92 }93 spfa();94 ans=0;95 for(int i=1;i<=cnt;i++)if(c[i])ans=max(ans,d[i]);96 printf("%lld\n",ans);97 return 0;98 }
16
1 5
1 4
4
3
5
6
Sample Output
47
HINT
50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
Source
BZOJ1179: [Apio2009]Atm
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。