洛谷P3627：https://www.luogu.org/problemnew/show/P3627
思路
由于有强连通分量 所以我们可以想到先把整个图缩点
缩点完之后再建一次图 把点权改为边权 并把边权转为负数 即可用SPFA求最短路间接求最长路了
最后我们查询所有的酒吧 跳出最大的ans即可
思路简单 但是代码有些冗长
代码
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 500010
int n,m,s,p,top,num,cnt,col,ans,t,w;
int h[maxn],de[maxn],st[maxn],dfn[maxn],low[maxn],co[maxn],money[maxn],sum[maxn],q[maxn],dis[maxn],x[maxn],y[maxn];
bool vis[maxn],exist[maxn];
struct Edge
{
int to;
int next;
int w;
}e[maxn];
void add(
int u,
int v)
//Tarjan的边
{
e[++cnt].to=
v;
e[cnt].next=
h[u];
h[u]=
cnt;
}
void read()
//输入
{
cin>>n>>
m;
for(
int i=
1;i<=m;i++
)
{
cin>>x[i]>>
y[i];
add(x[i],y[i]);
}
for(
int i=
1;i<=n;i++
)
cin>>
money[i];
cin>>
s;
}
void Add(
int u,
int v,
int w)
//SPFA的边
{
e[++cnt].w=
w;
e[cnt].to=
v;
e[cnt].next=
h[u];
h[u]=
cnt;
}
void Tarjan(
int u)
//标准Tarjan
{
dfn[u]=low[u]=++
num;
vis[u]=
1;
st[++top]=
u;
for(
int i=h[u];i;i=
e[i].next)
{
int v=
e[i].to;
if(!
dfn[v])
{
Tarjan(v);
low[u]=
min(low[u],low[v]);
}
else
if(vis[v])
{
low[u]=
min(low[u],dfn[v]);
}
}
if(dfn[u]==
low[u])
{
col++
;
while(st[top+
1]!=
u)
{
sum[col]+=money[st[top]];
//计算此强连通分量的总价值
co[st[top]]=
col;
vis[st[top--]]=
0;
}
}
}
void SPFA()
//标准SPFA
{
memset(dis,127,
sizeof(dis));
dis[co[s]]=-sum[co[s]];
//负权
q[
1]=co[s];
//把市中心所在的点入队
t=
0;
w=
1;
while(t<
w)
{
t++
;
int u=
q[t];
exist[u]=
0;
for(
int i=h[u];i;i=
e[i].next)
{
int v=
e[i].to;
if(dis[v]>dis[u]+
e[i].w)
{
dis[v]=dis[u]+
e[i].w;
if(!
exist[v])
{
w++
;
q[w]=
v;
exist[v]=
1;
}
}
}
}
}
int main()
{
read();
for(
int i=
1;i<=n;i++
)
if(!
dfn[i]) Tarjan(i);
cnt=
0;
memset(e,0,
sizeof(e));
memset(h,0,
sizeof(h));
//注意清空边
for(
int i=
1;i<=m;i++
)
if(co[x[i]]!=
co[y[i]])
Add(co[x[i]],co[y[i]],-sum[co[y[i]]]);
//负权边
SPFA();
cin>>
p;
for(
int i=
1;i<=p;i++)
//枚举所有酒吧求最大值
{
int bar;
cin>>
bar;
if(-dis[co[bar]]>
ans)
ans=-
dis[co[bar]];
}
cout<<
ans;
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9709954.html
相关资源：JAVA上百实例源码以及开源项目
