C++14(g++5.4) 解法, 执行用时: 311ms, 内存消耗: 47960K, 提交时间: 2019-11-01 15:20:11
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,s,p,qnum,top,visnum,cnt;
int head[500010],a[500010],low[500010],dfn[500010],st[500010],in[500010],belong[500010],sum[500010],dis[500010],x[500010],y[500010];
struct node{
int v,to,next;
}edge[1000010];
void add(int x,int y)
{
cnt++;
edge[cnt].to=y;
edge[cnt].next=head[x];
head[x]=cnt;
}
int read()
{
int x=0,w=1;char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;
}
void tarjan(int k)
{
int v;
dfn[k]=low[k]=++visnum;
in[k]=1;
st[++top]=k;
for(int i=head[k];i;i=edge[i].next)
{
v=edge[i].to;
if(!dfn[v])
{
tarjan(v);
low[k]=min(low[v],low[k]);
}
else if(in[v])
{
low[k]=min(low[k],dfn[v]);
}
}
v=0;
if(dfn[k]==low[k])
{
qnum++;
do
{
v=st[top--];
in[v]=0;
belong[v]=qnum;
sum[qnum]+=a[v];
}while(v!=k);
}
}
void spfa()
{
int l=0,r=1,k,v;
st[1]=s;in[s]=1,dis[s]=sum[s];
while(l<r)
{
l++;
k=st[l];
in[k]=0;
for(int i=head[k];i;i=edge[i].next)
{
v=edge[i].to;
if(dis[k]+sum[v]>dis[v])
{
dis[v]=dis[k]+sum[v];
if(!in[v])
{
r++;
st[r]=v;
in[v]=1;
}
}
}
}
}
int main()
{
int z;
n=read();m=read();
for(int i=1;i<=m;i++)
{
x[i]=read();y[i]=read();
add(x[i],y[i]);
}
for(int i=1;i<=n;i++)
{
a[i]=read();
}
s=read();p=read();
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i);
}
s=belong[s];
memset(head,0,sizeof(head));
cnt=0;
for(int i=1;i<=m;i++)
{
if(belong[x[i]]!=belong[y[i]])
add(belong[x[i]],belong[y[i]]);
}
memset(st,0,sizeof(st));
memset(in,0,sizeof(in));
spfa();
int ans=0;
for(int i=1;i<=p;i++)
{
z=read();
ans=max(ans,dis[belong[z]]);
}
cout<<ans;
}
C++(g++ 7.5.0) 解法, 执行用时: 452ms, 内存消耗: 46536K, 提交时间: 2023-04-16 10:39:23
#include<bits/stdc++.h>
using namespace std;
int n,m,s,p,cnt,co,num;
int h[500005],bb[500005],l[500005];
int top,wei;
struct node
{
int v,i,w,b;
}a[500005];
struct edge
{
int x,y,nt;
}e[500005];
void add(int x,int y)
{
e[++cnt].x=x;
e[cnt].y=y;
e[cnt].nt=h[x];
h[x]=cnt;
}
void dfs(int x)
{
a[x].i=a[x].w=++num;
a[x].v=1;
l[++top]=x;
for(int i=h[x]; i; i=e[i].nt)
{
int y=e[i].y;
if(a[y].i==0)
{
dfs(y);
if(a[y].w<a[x].w)
a[x].w=a[y].w;
}
else if(a[y].v==1)
if(a[y].i<a[x].w)
a[x].w=a[y].i;
}
if(a[x].i==a[x].w)
{
co++;
int k;
while(1)
{
k=l[top--];
a[k].v=0;
a[k].b=co;
if(k==x)
break;
}
}
}
void spfa()
{
for(int i=1;i<=co;i++)
a[i].v=a[i].w=0;
top=1;
wei=2;
l[1]=s;
a[s].w=bb[s];
a[s].v=1;
while(top!=wei)
{
int x=l[top];
for(int i=h[x];i>0;i=e[i].nt)
{
int y=e[i].y;
if(a[y].w<a[x].w+bb[y])
{
a[y].w=a[x].w+bb[y];
if(a[y].v==0)
{
a[y].v=1;
l[wei++]=y;
if(wei>co)wei=1;
}
}
}
a[x].v=0;
top++;
if(top>co)
top=1;
}
}
int main()
{
cin>>n>>m;
int x,y;
for(int i=1; i<=n; i++)
bb[i]=a[i].v=a[i].i=a[i].w=h[i]=0;
for(int i=1; i<=m; i++)
{
cin>>x>>y;
add(x,y);
}
for(int i=1; i<=n; i++)
if(a[i].i==0)
dfs(i);
for(int i=1; i<=n; i++)
{
cin>>x;
bb[a[i].b]+=x;
}
scanf("%d%d",&s,&p);
int ll=cnt;
cnt=0;
for(int i=1;i<=n;i++)
h[i]=0;
for(int i=1;i<=ll;i++)
{
x=e[i].x;
y=e[i].y;
if(a[x].b!=a[y].b)
add(a[x].b,a[y].b);
}
s=a[s].b;
spfa();
int ans=0;
for(int i=1;i<=p;i++)
{
cin>>x;
ans=max(ans,a[a[x].b].w);
}
printf("%d\n",ans);
return 0;
}
C++ 解法, 执行用时: 713ms, 内存消耗: 63248K, 提交时间: 2022-02-19 20:45:51
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 5e5 + 3;
int n,m,atm[maxn],c[maxn],size_[maxn],group[maxn],in[maxn],f[maxn];
unsigned int dfn[maxn],low[maxn],d,s[maxn],top,cnt;
vector <int> g[maxn],rg[maxn];
queue <int> q;
void tarjan(const int &x){
dfn[x] = low[x] = ++d;
s[++top] = x;
for (int i = 0;i < g[x].size();i++)
if (!dfn[g[x][i]]){
tarjan(g[x][i]);
low[x] = min(low[x],low[g[x][i]]);
}else if (!group[g[x][i]])
low[x] = min(low[x],low[g[x][i]]);
if (dfn[x] == low[x]){
cnt++;
size_[cnt] = atm[x];
group[x] = cnt;
while (s[top] != x){
size_[cnt] += atm[s[top]];
group[s[top]] = cnt;
top--;
}
top--;
}
}
int main(){
cin>>n>>m;
int s,p,ans = 0,i,j;
while (m--){
cin>>s>>p;
g[s].push_back(p);
}
for (i = 1;i <= n;i++)
cin>>atm[i];
cin>>s>>p;
for (i = 1;i <= p;i++){
cin>>c[i];
}
tarjan(s);
for (i = 1;i <= n;i++)
if (dfn[i]){
for (j = 0;j < g[i].size();j++)
if (group[g[i][j]] != group[i]){
rg[group[i]].push_back(group[g[i][j]]);
in[group[g[i][j]]]++;
}
}
q.push(group[s]);
f[group[s]] = size_[group[s]];
while (!q.empty()){
i = q.front();
q.pop();
for (j = 0;j < rg[i].size();j++){
f[rg[i][j]] = max(f[rg[i][j]],f[i] + size_[rg[i][j]]);
if (!--in[rg[i][j]])
q.push(rg[i][j]);
}
}
for (i = 1;i <= p;i++)
ans = max(ans,f[group[c[i]]]);
cout<<ans;
return 0;
}
市中心在路口1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表示。每个ATM机中可取的钱数标在了路口的上方。在这个例子中，Banditji能抢劫的现金总数为47，实施的抢劫路线是：1-2-4-1-2-3-5。