[BZOJ1179][APIO2009][强连通分量Tarjan+spfa]ATM
2024-09-25 21:51:25
[BZOJ1179][APIO2009]ATM
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的单向的道路到达其中的至少一个酒吧。
题目大意:在一个各个点都有权值有向图中,从一个点出发,走过的点权值清零。要求问如何走所得的总权值最大,并且可以在酒吧点结束。
题目分析:如果若干个点处在同一个强连通分量中,那么从这个强连通分量中任意一个节点出发必定能到达这个强连通分量中的任意一个点。所以可以把这些点用Tarjan缩成一个点,把强连通分量中的所有的点权加到那个缩成的点,然后把这些缩成的点重构图跑一遍spfa,输出到所有酒吧点的路中最长的即可。
下面贴AC代码:
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,cnt,re_cnt,S,P,CN,maxn,top,dfs_num;
int pre[],re_pre[],bar[],DFN[],LOW[],dye[],size[],tow[],vis[],w[],dist[];
struct pack{int to,next,d;} E[],re_E[];
void add_edge(int x,int y){
E[++cnt].to=y;
E[cnt].next=pre[x];
pre[x]=cnt;
}
void rebuild(){
for(int i=;i<=n;++i)
for(int j=pre[i];j;j=E[j].next)
if(dye[i]!=dye[E[j].to]&&dye[i]&&dye[E[j].to]){
re_E[++re_cnt].to=dye[E[j].to];
re_E[re_cnt].next=re_pre[dye[i]];
re_E[re_cnt].d=size[dye[E[j].to]];
re_pre[dye[i]]=re_cnt;
}
}
void tarjan(int pos){
vis[tow[++top]=pos]=;
DFN[pos]=LOW[pos]=++dfs_num;
for(int i=pre[pos];i;i=E[i].next){
if(!DFN[E[i].to]){
tarjan(E[i].to);
LOW[pos]=min(LOW[pos],LOW[E[i].to]);
}
else if(vis[E[i].to])
LOW[pos]=min(LOW[pos],DFN[E[i].to]);
}
if(DFN[pos]==LOW[pos]){
vis[pos]=;
size[dye[pos]=++CN]+=w[pos];
while(pos!=tow[top]){
size[dye[tow[top]]=CN]+=w[tow[top]];
vis[tow[top--]]=;
}
--top;
}
}
int spfa(int pos){
vis[pos]=;
for(int i=re_pre[pos];i;i=re_E[i].next){
int v=re_E[i].to; int k=re_E[i].d;
if(dist[pos]+k>dist[v]){
dist[v]=dist[pos]+k;
if(!vis[v]){
if(spfa(re_E[i].to)) return ;
}
else return ;
}
}
vis[pos]=;
return ;
}
int main(){
scanf("%d%d",&n,&m);
if(!n||!m) {printf("");return ;}
for(int i=;i<=m;++i){
int a,b;
scanf("%d%d",&a,&b);
add_edge(a,b);
}
for(int i=;i<=n;++i)
scanf("%d",&w[i]);
scanf("%d%d",&S,&P);
for(int i=;i<=P;++i){
int t;
scanf("%d",&t);
bar[t]=;
}
for(int i=;i<=n;++i)
if(!dye[i])
tarjan(i);
rebuild();
dist[dye[S]]=size[dye[S]];
spfa(dye[S]);
for(int i=;i<=n;++i)
if(bar[i])
if(dist[dye[i]]>maxn)
maxn=dist[dye[i]];
printf("%d",maxn);
return ;
}
最新文章
- 原生js焦点轮播图
- 在webstorm设置File watcher for Jade
- python列表、元祖、字典
- 微软发布WP SDK8.0 新增语音、应用内支付等原生API
- laravel扩展xls处理maatwebsite/excel
- jq實現網頁個性title
- SQL-Delete Duplicate Emails
- [转]用python 10min手写一个简易的实时内存监控系统
- JAVA线程池学习,ThreadPoolTaskExecutor和ThreadPoolExecutor有何区别?
- window64位电脑如何通过VMware Workstation12.5.6安装苹果操作系统 macOS High Sierra 10.13
- gulp结合Thinkphp配置
- 5Linux流程控制语句-if、for、while、case语句、计划任务
- nltk-贝叶斯分类器
- kruskal(拓展)
- Windows 命令行解析工具(getopt)
- JavaScript使用浏览器内置XML解析器解析DOM对象
- C++点和箭头操作符用法区别
- Oracle EBS AR 事务处理到期余额总计API
- Noip前的大抱佛脚----根号对数算法
- CSS级联样式表-css选择器