SPFA | OceanEye's Blog

BZOJ1179

老题。
强连通分量把能一起抢的缩成一个点
然后在图上跑SPFA或者DP都可以
写SPFA写惯了……

/**************************************************************
    Problem: 1179
    User: OceanEYe
    Language: C++
    Result: Accepted
    Time:9392 ms
    Memory:42020 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
 
char cc; int C;
template <class T>
void read( T &x )
{
    x=0; cc=getchar(); C=1;
    while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
    while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
    x*=C;
}
 
using namespace std;
#define N 500010
 
int fa[N];
#define S 0
#define T n+5
vector <int> G[N];
 
int n,m,val[N],s,TT[N];
bool p[N];
 
void pre()
{
    int _,__;
    read(n); read(m);
    for(int i=1;i<=m;i++)
    {
        read(_); read(__);
        G[_].push_back(__);
    }
    for(int i=1;i<=n;i++)
        read(val[i]);
    read(s); read(__);
    for(int i=1;i<=__;i++)
    {
        read(_); p[_]=true;
    }
}
 
int STA[N],top,SSTA[N],TOP;
int dfn[N],low[N],cur[N],in[N],tot;
bool inSTA[N],vis[N];
 
void Tarjan(int x)
{
    SSTA[++TOP]=x;
    low[x]=dfn[x]=++top;
    STA[top]=x;
    fa[x]=x;
    vis[x]=true;
    inSTA[x]=true;
    bool flag;
    for(;TOP;)
    {
        flag=true;
        int u=SSTA[TOP];
        for(int i=cur[u];i<G[u].size();i++)
        {
            if(!vis[G[u][i]])
            {
                vis[G[u][i]]=true;
                fa[G[u][i]]=u;
                low[G[u][i]]=dfn[G[u][i]]=++top;
                STA[top]=G[u][i];
                inSTA[G[u][i]]=true;
                SSTA[++TOP]=G[u][i];
                cur[u]=i+1;
                flag=false;
                break;
            }
            else continue;
        }
        if(!flag) continue;
        for(int i=0;i<G[u].size();i++)
            if(fa[G[u][i]]==u) low[u]=min(low[u],low[G[u][i]]);
            else if(inSTA[G[u][i]]) low[u]=min(low[u],dfn[G[u][i]]);
        if(low[u]==dfn[u])
        {
            tot++;
            while(top!=dfn[u])
            {
                in[STA[top]]=tot;
                inSTA[STA[top]]=false;
                TT[tot]+=val[STA[top--]];
            }
            in[STA[top]]=tot;
            inSTA[STA[top]]=false;
            TT[tot]+=val[u]; top--;
        }
        TOP--;
    }
}
 
vector <int> MP[N];
bool inq[N];
int dist[N];
 
int solve()
{
    queue <int> Q;
    Q.push(S); inq[S]=true;
    while(!Q.empty())
    {
        int x=Q.front(); inq[x]=false; Q.pop();
        for(int i=0;i<MP[x].size();i++)
        {
            if(dist[MP[x][i]] < dist[x] + TT[MP[x][i]])
            {
                dist[MP[x][i]]=dist[x] + TT[MP[x][i]];
                if(!inq[MP[x][i]]) Q.push(MP[x][i]),inq[MP[x][i]]=true;
            }
        }
    }
    return dist[T];
}
 
int main()
{
    pre();
    Tarjan(s);
    for(int i=1;i<=n;i++)
    {
        if(!in[i]) continue;
        for(int j=0;j<G[i].size();j++)
        {
            if(in[G[i][j]]==in[i]) continue;
            MP[in[i]].push_back(in[G[i][j]]);
        }
    }
    MP[S].push_back(in[s]);
    for(int i=1;i<=n;i++)
        if(p[i]) MP[in[i]].push_back(T);
    printf("%d",solve());
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

/**************************************************************

Problem: 1179

User: OceanEYe

Language: C++

Result: Accepted

Time:9392 ms

Memory:42020 kb

****************************************************************/

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <queue>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 500010

int fa[N];

#define S 0

#define T n+5

vector <int> G[N];

int n,m,val[N],s,TT[N];

bool p[N];

void pre()

{

int _,__;

read(n); read(m);

for(int i=1;i<=m;i++)

{

read(_); read(__);

G[_].push_back(__);

}

for(int i=1;i<=n;i++)

read(val[i]);

read(s); read(__);

for(int i=1;i<=__;i++)

{

read(_); p[_]=true;

}

int STA[N],top,SSTA[N],TOP;

int dfn[N],low[N],cur[N],in[N],tot;

bool inSTA[N],vis[N];

void Tarjan(int x)

{

SSTA[++TOP]=x;

low[x]=dfn[x]=++top;

STA[top]=x;

fa[x]=x;

vis[x]=true;

inSTA[x]=true;

bool flag;

for(;TOP;)

{

flag=true;

int u=SSTA[TOP];

for(int i=cur[u];i<G[u].size();i++)

{

if(!vis[G[u][i]])

{

vis[G[u][i]]=true;

fa[G[u][i]]=u;

low[G[u][i]]=dfn[G[u][i]]=++top;

STA[top]=G[u][i];

inSTA[G[u][i]]=true;

SSTA[++TOP]=G[u][i];

cur[u]=i+1;

flag=false;

break;

}

else continue;

}

if(!flag) continue;

for(int i=0;i<G[u].size();i++)

if(fa[G[u][i]]==u) low[u]=min(low[u],low[G[u][i]]);

else if(inSTA[G[u][i]]) low[u]=min(low[u],dfn[G[u][i]]);

if(low[u]==dfn[u])

{

tot++;

while(top!=dfn[u])

{

in[STA[top]]=tot;

inSTA[STA[top]]=false;

TT[tot]+=val[STA[top--]];

}

in[STA[top]]=tot;

inSTA[STA[top]]=false;

TT[tot]+=val[u]; top--;

}

TOP--;

}

vector <int> MP[N];

bool inq[N];

int dist[N];

int solve()

{

queue <int> Q;

Q.push(S); inq[S]=true;

while(!Q.empty())

{

int x=Q.front(); inq[x]=false; Q.pop();

for(int i=0;i<MP[x].size();i++)

{

if(dist[MP[x][i]] < dist[x] + TT[MP[x][i]])

{

dist[MP[x][i]]=dist[x] + TT[MP[x][i]];

if(!inq[MP[x][i]]) Q.push(MP[x][i]),inq[MP[x][i]]=true;

}

return dist[T];

}

int main()

{

pre();

Tarjan(s);

for(int i=1;i<=n;i++)

{

if(!in[i]) continue;

for(int j=0;j<G[i].size();j++)

{

if(in[G[i][j]]==in[i]) continue;

MP[in[i]].push_back(in[G[i][j]]);

}

MP[S].push_back(in[s]);

for(int i=1;i<=n;i++)

if(p[i]) MP[in[i]].push_back(T);

printf("%d",solve());

return 0;

}

BZOJ1179

SPFA的几个优化

OceanEye 撰写 SPFA 最短路无回复

SPFA自问世以来，就一直活跃在奥赛各界。因为其极其优化的复杂度和很短的编写代码，各大OI主流媒体都称其为最短路利器。但是，有人闲来无聊之时，在举办模拟赛的时候，会用大量的功夫用于卡掉普通的SPFA(个人觉得比较蛋疼，按理来说是不应该阻碍新技术的推广)。使用我收集了几个比较常见的优化，可以优化SPFA，更重要的是，这个就如随机化快排一般，使SPFA不太会受数据的限制。

1.循环队列

循环队列是因为SPFA的另一个优化，对于队列中已经存在的点，在SPFA的拓展过程中，这个点是不能重复加入的。这样的话，最坏的情况是所有的点都在队列中，队列长度最多与N同级别。这时，可以用循环队列保证队列的长度于N同级别。实现方法就是在head，tail的更新过程中，如果发现大于队列最大允许长度，那么就将其变为1。因为head，tail每次最多加1，所以这样做就可以了。需要注意的是，SPFA的结束条件要变为Head=Tail，有些同学喜欢写Head>=Tail，如果写循环队列的话，这样写是有可能出错的。

2.SLF即Small Label First策略。

实现的方法很简单，即当你要向队列中添加节点的时候，先将其与队首元素比较，如果其比队首元素要优（当前已知的最短距离更小一些），那么将其放在队首的位置，否则放到队尾。这样保证较小距离的节点优先得到拓展。可以使SPFA更快的结束。

3.LLL即Large Label Last 策略。

表示不会，请移步这里。

4.还有一个不知名的优化（没有验证过）

若当前元素没有目标节点优，则不更新。

以上。

转自：http://www.blogbus.com/oibltx-logs/125657995.html

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ1179

BZOJ1179

@OceanEye7年前

SPFA的几个优化

SPFA的几个优化

友情链接

近期文章

标签