APIO2017商旅
2021-03-22 15:35
标签：分数规划 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