APIO2017商旅

传送门(PDF)

题目大意:有$N$个点，$M$条有向边，$K$种物品，在不同的点可以用不同的价格买入或卖出某一种商品。

任意时刻至多持有一种物品，不能在同一个点先买再卖，求收益与长度之比最大的点数$\geq 2$的回路(可以不进行任何买卖)。

$N,M\leq 100，K\leq 1000，M\leq 9900$

比值最大，显然是一道分数规划的题目，难点在于建图。

如果直接在每一个点买卖分类拆点，模拟行走的过程，点数将达到$10^5$数量级，而图本身趋近于完全图，所以建图本身就会炸掉。

不难发现一个结论：从某$A$点买东西再到$B$点卖出，一定会走其最短的路径。所以，我们不妨模拟买卖的过程。

假设当前二分的比值是$x$，则点$A$到点$B$的距离就是$T(A,B)-x\times Dis(A,B)$

其中$T(A,B)=$在$K$种商品中在$A$买入在$B$卖出获得的最大利润(与$0$取最大值，因为可以不进行买卖)

$Dis(A,B)=$从$A$到$B$的最短路。

对于$T(x,y)$，直接暴力枚举每个点对和每种商品，复杂度$O(N^2K)$

对于$Dis(x,y)$，可以使用$Floyd$预处理，复杂度$O(N^3)$。

所以最终的复杂度是$O(N^2K+N^3+log(V)\cdot($求非负$($正$)$环$))$。

在求正负环时，可以采用$Bfs$和$Dfs$两种写法的$SPFA$，对于随机图，$Dfs$版本通常情况下复杂度更优，但是本题图为稠密图，而且点数较少，还是推荐使用更为稳定的$Bfs$写法的$SPFA$，复杂度下限为$O(n^3)$。

AC代码如下

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define INF 2000000000000000ll

#define M 200020

#define N 303

using namespace std;

LL read(){

	LL nm=0,fh=1;char cw=getchar();

	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;

	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');

	return nm*fh;

}

LL n,m,K,G[N][N],T[N][N],B[N][1020],S[N][1020],dis[N],ind[N];

LL fs[N],nt[M],to[M],u,v,tmp,L,R,md,ans,hd,tl,q[M];

bool vis[N];

void link(LL x,LL y){nt[tmp]=fs[x],fs[x]=tmp,to[tmp++]=y;}

void init(){

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

		for(int j=1;j<=n;j++){

			if(i==j) continue;

			for(int k=1;k<=K;k++){

				if(B[i][k]<0||S[j][k]<0) continue;

				T[i][j]=max(T[i][j],S[j][k]-B[i][k]);

			}

		}

	}

	for(int k=1;k<=n;k++){

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

			for(int j=1;j<=n;j++) G[i][j]=min(G[i][j],G[i][k]+G[k][j]);

		}

	}

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

		for(int j=1;j<=n;j++) if(i!=j&&G[i][j]<INF) link(i,j);

	}

}

bool check(LL now){

	for(int i=1;i<=n;i++) dis[i]=ind[i]=0;

	for(int i=1;i<=n;i++) q[tl++]=i,vis[i]=true;

	while(hd<tl){

		LL x=q[hd++]; vis[x]=false;

		for(int i=fs[x];i!=-1;i=nt[i]){

			LL len=T[x][to[i]]-now*G[x][to[i]];

			if(dis[to[i]]>dis[x]+len) continue;

			dis[to[i]]=dis[x]+len;

			if(!vis[to[i]]){

			    vis[to[i]]=true,q[tl++]=to[i];

			    if(++ind[to[i]]>n) return true;

			}

		}

	}

	return false;

}

void solve(){

	L=1ll,R=10000000000ll;

	while(L<=R){

		md=((L+R)>>1),hd=tl=0;

		if(check(md)) ans=md,L=md+1;

		else R=md-1;

	}

}

int main(){

	n=read(),m=read(),K=read();

	for(int i=1;i<=n;G[i][i]=0,fs[i++]=-1){

	    for(int j=1;j<=n;j++) G[i][j]=INF,T[i][j]=0;

		for(int j=1;j<=K;j++) B[i][j]=read(),S[i][j]=read();

	}

	for(LL i=1;i<=m;i++) u=read(),v=read(),tmp=read(),G[u][v]=min(G[u][v],tmp);

	tmp=0,init(),solve(),printf("%lld\n",ans);

	return 0;

}

巴特西

APIO2017商旅

最新文章

热门文章