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}\)。
近期评论