SPFA 算法的优化的练习题。
对应 OJ 的传送门。
《高手训练》解题报告集合：信息学奥赛一本通·高手训练。
未完待续
SPFA 算法的优化
SPFA 算法的优化有两种，但是这不是本文的重点。
均值最小环 B
时空限制：\(1\texttt{s},128\texttt{MiB}\)。
题目描述
画一个 \(n\) 个节点，\(m\) 条边的带权有向图，想从中找出权值的平均值最小的环。有向图中可能不存在环，求最小的平均权值。
数据范围
对于 \(100\%\) 的数据，\(1\leq n\leq 10^3\)，\(1\leq m\leq 10^4\)，\(0\leq w\leq 10^7\)。
题解
显然是 分数规划 问题，直接用 二分+\(\texttt{spfa}\) 判负环 即可。
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=1e3+5;
const int MAXM=1e4+5;
const double eps=1e-4;
const double inf=1e8;
int n,m;
int cnt,head[MAXN],to[MAXM],w[MAXM],Next[MAXM];
inline void Add_Edge(reg int u,reg int v,reg int len){
Next[++cnt]=head[u];
to[cnt]=v;
w[cnt]=len;
head[u]=cnt;
return;
}
bool vis[MAXN];
double dis[MAXN];
inline bool spfa(reg int u,reg double mid){
vis[u]=true;
for(reg int i=head[u];i;i=Next[i]){
reg int v=to[i];
if(dis[u]+w[i]-mid>=dis[v])
continue;
if(vis[v]&&dis[u]+w[i]-mid<=0)
return true;
dis[v]=dis[u]+w[i]-mid;
if(!vis[v]&&spfa(v,mid))
return true;
}
vis[u]=false;
return false;
}
inline bool check(reg double mid){
for(reg int i=1;i<=n;++i)
vis[i]=false,dis[i]=0;
for(reg int i=1;i<=n;++i)
if(!dis[i]&&spfa(i,mid))
return true;
return false;
}
double l=inf,r=-inf,mid;
int main(void){
n=read(),m=read();
for(reg int i=1;i<=m;++i){
static int u,v,w;
u=read(),v=read(),w=read();
Add_Edge(u,v,w);
l=min(l,1.0*w),r=max(r,1.0*w);
}
reg bool flag=false;
while(r-l>=eps){
mid=0.5*(l+r);
if(check(mid))
flag=true,r=mid;
else
l=mid;
}
if(!flag)
puts("PaPaFish is laying egg!");
else
printf("%.2lf\n",l);
return 0;
}
最小边权和 ha
时空限制：\(1\texttt{s},512\texttt{MiB}\)。
题目描述
有一张 \(n\) 个点 \(m\) 条边的有向图，每条边有一个互不相同的边权 \(w\)，有 \(q\) 个询问，要求你从点 \(a\) 经过不超过 \(c\) 条边到点 \(b\)，要求经过的边权不下降且和尽量小，求出满足条件的最小的边权和，如果没有合法方案则输出 \(−1\)。
数据范围
对于 \(100\%\) 的数据，\(n\leq 150\)，\(m\leq 5\times 10^3\)，\(q\leq 10^3\)，\(w\leq 5\times 10^3\)。
题解
首先按照边权排序，不妨设 \(f_{i,j,k}\) 表示从 \(i\) 到 \(j\) 恰好经过 \(k\) 条边且边权单调不降的最短路，那么我们可以用 \(\texttt{Bellman-Ford}\) 的方式转移得到 \(f\) 数组，进一步地，我们对 \(f\) 数组做前缀最小值，那么\(f_{i,j,k}\) 表示从 \(i\) 到 \(j\) 不超过 \(k\) 条边且边权单调不降的最短路，询问时直接输出即可。
问题来了，为什么我们要把路径数 \(k\) 这个状态数放在第三个维度呢（一般状态数在第一维）?
这与冯·诺依曼的计算机结构有关，我们把 \(k\) 放在第三维可以使得每次访问的内存空间连续，进而利用缓存机制提高速度（约 \(3\) 倍）。
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=150+5;
const int MAXM=5e3+5;
const int inf=0x3f3f3f3f;
struct Edge{
int u,v,w;
inline Edge(reg int u=0,reg int v=0,reg int w=0):u(u),v(v),w(w){
return;
}
inline bool operator<(const Edge& a)const{
return w<a.w;
}
};
int n,m,q;
int f[MAXN][MAXN][MAXN];
Edge E[MAXM];
inline void cMin(reg int& a,reg int b){
if(a>b)
a=b;
return;
}
int main(void){
n=read(),m=read(),q=read();
memset(f,0x3f,sizeof(f));
for(reg int i=1;i<=m;++i)
E[i].u=read(),E[i].v=read(),E[i].w=read();
sort(E+1,E+m+1);
for(reg int i=1;i<=n;++i)
f[i][i][0]=0;
for(reg int k=1;k<=m;++k)
for(reg int i=1;i<=n;++i)
for(reg int j=1;j<=n;++j)
cMin(f[i][E[k].v][j],f[i][E[k].u][j-1]+E[k].w);
for(reg int k=1;k<=n;++k)
for(reg int i=1;i<=n;++i)
for(reg int j=1;j<=n;++j)
cMin(f[i][j][k],f[i][j][k-1]);
while(q--){
static int a,b,c;
a=read(),b=read(),c=read();
cMin(c,n);
if(f[a][b][c]==inf)
puts("-1");
else
printf("%d\n",f[a][b][c]);
}
return 0;
}
骑士游戏 BZOJ3875
时空限制：\(3\texttt{s},256\texttt{MiB}\)。
近期评论