APIO2017商旅

2021-03-22 15:35

阅读：532

标签：分数规划 bsp pdf dig ace mil 拆点 tps tmp

传送门(PDF)

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

任意时刻至多持有一种物品，不能在同一个点先买再卖，求收益与长度之比最大的点数$\leq 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
#include
#include
#include
#include
#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;idis[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>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

APIO2017商旅

标签：分数规划 bsp pdf dig ace mil 拆点 tps tmp

原文地址：https://www.cnblogs.com/OYJason/p/9482554.html

上一篇：Windows Trigger Mail Sending Script

下一篇：python headers请求头快速添加

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：APIO2017商旅
文章链接：http://soscw.com/essay/67597.html

亲，登录后才可以留言！

APIO2017商旅

评论

热门文章

推荐文章

最新文章

置顶文章