【tarjan+SPFA】BZOJ1179-[Apio2009]Atm
2024-10-13 21:09:04
【题目大意】
给出一张有点权的有向图,已知起点和可以作为终点的一些点,问由起点出发,每条边和每个点可以经过任意多次,经过点的权值总和最大为多少。
【思路】
由于可以走任意多次,显然强连通分量可以缩点。然后就是一张DAG图,跑SPFA最长路就好了。
听说Dijkstra写最长路会发生一些奇特的化学反应并且炸掉,还没想清楚姑且笔记一下。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=+;
struct edge
{
int to,len;
};
int n,m,s,p,money[MAXN],bar[MAXN],u[MAXN],v[MAXN];
vector<int> E[MAXN];
vector<edge> rE[MAXN];
stack<int> S;
queue<int> que;
int instack[MAXN],low[MAXN],dfn[MAXN],sum[MAXN],col[MAXN],cnt,tot;
int dis[MAXN],inque[MAXN]; void addedge(int u,int v)
{
E[u].push_back(v);
} void addedge2(int u,int v,int w)
{
rE[u].push_back((edge){v,w});
} void tarjan(int x)
{
dfn[x]=low[x]=++cnt;
instack[x]=;
S.push(x);
for (int i=;i<E[x].size();i++)
{
int to=E[x][i];
if (!instack[to])
{
tarjan(to);
low[x]=min(low[x],low[to]);
}
else if (instack[to]==)
{
low[x]=min(low[x],dfn[to]);
}
} if (dfn[x]==low[x])
{
tot++;
int tmp;
do
{
tmp=S.top();S.pop();
sum[tot]+=money[tmp];
col[tmp]=tot;
instack[tmp]=;
}while (tmp!=x);
}
} void spfa(int start)
{
memset(inque,,sizeof(inque));
for (int i=;i<=tot;i++) dis[i]=;
dis[start]=sum[start];
inque[start]=;
que.push(start);
while (!que.empty())
{
int head=que.front();que.pop();
inque[head]=;
for (int i=;i<rE[head].size();i++)
{
int to=rE[head][i].to,len=rE[head][i].len;
if (dis[to]<dis[head]+len)
{
dis[to]=dis[head]+len;
if (!inque[to])
{
inque[to]=;
que.push(to);
}
}
}
}
} void rebuild()
{
for (int i=;i<=m;i++)
if (col[u[i]]!=col[v[i]]) addedge2(col[u[i]],col[v[i]],sum[col[v[i]]]);
} void init()
{
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
addedge(u[i],v[i]);
}
for (int i=;i<=n;i++) scanf("%d",&money[i]);
memset(bar,,sizeof(bar));
scanf("%d%d",&s,&p);
for (int i=;i<=p;i++)
{
int nowp;
scanf("%d",&nowp);
bar[nowp]=;
}
} void solve()
{
cnt=tot=;
memset(instack,,sizeof(instack));
for (int i=;i<=n;i++)
if (!instack[i]) tarjan(i);
rebuild();
spfa(col[s]);
int ans=-;
for (int i=;i<=n;i++)
if (bar[i]) ans=max(ans,dis[col[i]]);
printf("%d",ans);
} int main()
{
init();
solve();
return ;
}
最新文章
- [C#][算法] 用菜鸟的思维学习算法 -- 马桶排序、冒泡排序和快速排序
- job console部署
- 前端模板之EasyUI常用控件及参数
- Struts2之Struts2-2.5.5 Interceptor
- A cost-effective recommender system for taxi drivers
- PIC32MZ tutorial -- Input Capture
- ASP.NET 去除所有HTML标记的方法
- 一次 php nusoap 调试过程
- iptables 下开放ftp
- 591 - Box of Bricks
- jQuery插件实现的方法和原理简单说明
- 一个还算简单的微信消息SDK(基于.Net Standard 2.0)
- jenkins~集群分发功能和职责处理
- java 单例模式-饿懒汉模式
- codefroces 55D Beautiful numbers
- git cmd 命令在已有的仓库重新添加新的文件夹
- notepad++64位添加plugin manager
- WINDOWS中, 如何查看一个运行中的程序是64位还是32位的
- go语言net包udp socket的使用
- codeforces 235 div2 A. Vanya and Cards