《高手训练》解题报告 3.3 SPFA 算法的优化

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}\)。

题目描述