题意描述

[BOI 2002]双调路径

题意描述的确实不是很清楚（出题人惜字如金）。

给定一张有 \(n\) 个点，\(m\) 条边的无向图，每条边有两个权值，分别表示经过这个点的代价和时间。

同时给出起点 \(s\) 和终点 \(t\)，显然 \(s\to t\) 的路径有很多条。

其中说路径 A 比路径 B 更优，当且仅当 A 的代价和时间都小于 B。

当没有路线比这条路线更优时，称这条路线为最优路线。题目要求求 \(s\to t\) 的最优路线的条数。

注意：这里的最优路线可以有很多条，如果 \(time_A>time_B\) 但是 \(price_A<price_B\) 则两者谁也不优于谁。

同时，当两条路线代价和时间都相等时，成这两条路线为一条。（这里很良心了）

算法分析

基本思路

这里是双权值的最短路问题，比较直接的方法是以代价为关键字来枚举路径，每次选取时间最小的路径即可。

但是可以发现这种暴力算法将耗费大量时间用于判断代价是否相同，时间复杂度将非常恐怖，所以当场枪毙。

当时这种思想也给了我们启发，一番整理后有了一个可行的思想：

令 \(dis(i,j)\) 表示从 \(s\) 到 \(i\) 的代价为 \(j\) 的最短时间，那么显然有递推式：

\[dis(i,j)=min_{k\to i\in E}\{dis(k,j-price_{k,i})+time_{k,i}\}
\]

统计答案时，我们一次遍历 \(dis(t,i)(0\leq i\leq 10000)\)。（其中 10000 为数据范围内的最大代价）

同时维护一个 \(mn\) 表示当前时间的最小值，当 \(dis(t,i)<mn\) 时，更新 \(mn\) 并且令 ans++。

这就表示：当一条路径的代价比你大（从小到大枚举）但时间比你少时，这是最优路径之一。

然后再时限放宽之后应该就是可以过了。（2020.4.22）

时间优化

但是在之前，这还是一道紫题的时候...，它的实现是 0.1s，这么“滥用”最短路肯定是过不去的。

那怎么办呢？

可以发现，根据 OI 定理：当一个人比你小还比你强时，你就可以退役了。

换句话说：如果在你之前存在一条路径，代价和时间都比你小，那么你不可能是最优路径。

不仅如此，你所拓展的路径也不可能是最优路径。（自证不难）

所以我们可以利用树状数组进行优化，记录下区间最小值即可。（记得是二位树状数组）

代码实现

实现比较简单，说实话思路也没有难到哪里去。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cmath>

#include<queue>

#include<algorithm>

#define N 1100

#define M 3100

#define C 10010

using namespace std;

int n,m,s,t,head[N],cnt=0,dis[N][C],tree[N][C];

bool vis[N][C];

struct Edge{

	int nxt,to,w1,w2;

}ed[M<<1];

int read(){

	int x=0,f=1;char c=getchar();

	while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();

	while(c>='0' && c<='9') x=x*10+c-48,c=getchar();

	return x*f;

}

void add(int u,int v,int c,int t){

	ed[++cnt].nxt=head[u];

	ed[cnt].to=v,ed[cnt].w1=c,ed[cnt].w2=t;

	head[u]=cnt;

	return;

}

int lowbit(int x){return x&(-x);}

void change(int x,int y,int z){

	y++;

	while(y<10100){

		tree[x][y]=min(tree[x][y],z);

		y+=lowbit(y);

	}

	return;

}

int ask(int x,int y){

	y++;

	int mn=0x7fffffff;

	while(y>=1){

		mn=min(mn,tree[x][y]);

		y-=lowbit(y);

	}

	return mn;

}

void spfa(){

	queue<pair<int,int> >q;

	memset(dis,0x3f,sizeof(dis));

	memset(tree,0x3f,sizeof(tree));

	memset(vis,false,sizeof(vis));

	dis[s][0]=0;

	vis[s][0]=true;

	q.push(make_pair(s,0));

	change(s,0,0);

	while(!q.empty()){

		int w=q.front().second,u=q.front().first;

		q.pop();

		vis[u][w]=false;

		for(int i=head[u];i;i=ed[i].nxt){

			int v=ed[i].to;

			int w1=ed[i].w1,w2=ed[i].w2;

			int ww=w+w1;

			if(ask(v,ww)>dis[u][w]+w2){

				dis[v][ww]=dis[u][w]+w2;

				change(v,ww,dis[v][ww]);

				if(!vis[v][ww])

					q.push(make_pair(v,ww)),vis[v][ww]=true;

			}

		}

	}

	return;

}

int main(){

	n=read(),m=read(),s=read(),t=read();

	int u,v,w1,w2;

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

		u=read(),v=read(),w1=read(),w2=read();

		add(u,v,w1,w2),add(v,u,w1,w2);

	}

	spfa();

    int mmin = 0x3f3f3f3f, ans = 0;

    for (int i = 0; i <= 10000; i++) {

		if (dis[t][i] < mmin)

            mmin = dis[t][i], ans++;

    }

	printf("%d\n",ans);

	return 0;

}

完结撒花

巴特西

P5530 [BOI 2002]双调路径

题意描述

算法分析

基本思路

时间优化

代码实现

最新文章

热门文章