【bzoj4898】[Apio2017]商旅 Floyd+分数规划+Spfa

2021-05-12 16:29

阅读：598

标签：再处理 memset namespace turn ... lin 无法 long cstring

题目描述

有n个点、m条边、和k种商品。第$i$个点可以以$B_{ij}$的价格买入商品$j$，并以$S_{ij}$的价格卖出。任何时候只能持有一个商品。求一个环，使得初始不携带商品时以某种交易方式走过一圈所得的利润/路径长度（向下取整）最大。

输入

第一行包含3个正整数N,M和K,分别表示集市数量、道路数量和商品种类数量。

接下来的N行，第行中包含2K个整数描述一个集市Bi,1 Si,1 Bi,2 Si,2...Bik Si,k。

对于任意的1

如果一个交易价格为-1，则表示这个商品在这个集市上不能进行这种交易。

接下来M行，第行包含3个整数Vp,Wp和Tp,表示存在一条从编号为Vp的市场出发前往编号为Wp的市场的路径花费Tp分钟。

如果在编号为的集市i中，编号为j的商品既可以购买又可以卖出则0

对于编号为P(1Wp且1

不存在满足1

输出

输出包含一个整数，表示盈利效率最高的环路盈利效率，答案向下取整保留到整数。如果没有任何一条环路可以盈利，则输出0。

样例输入

4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

样例输出

题解

Floyd+分数规划+Spfa

题目显然是一个分数规划的模型，但是如果直接使用分层图模拟商品买卖的过程的话肯定会TLE。

我们不妨换个思路：考虑每件两点之间的连续交易。即在A地购买商品，并在B地卖出的这个过程。

那么这个过程走的一定是最短路，买卖的一定是盈利最大的商品（当无法盈利时显然不进行买卖，盈利为0）。

所以可以使用Floyd求出任意两点之间最短路，再处理出来任意两点之间的最大盈利。

然后就可以对这个图求最大比率环了。二分答案，把每条边的权值看作最大盈利-最短路*mid ，如果有非负环则说明mid成立，否则mid不成立。

时间复杂度$O(n^2k+n^3\log v)$。

#include 
#include 
#include 
#define N 110
#define K 1010
using namespace std;
typedef long long ll;
queue q;
int n , len[N][N] , val[N][N] , b[N][K] , s[N][K] , inq[N] , num[N];
ll dis[N];
inline bool judge(int mid)
{
	int x , i;
	while(!q.empty()) q.pop();
	for(i = 1 ; i > 1;
		if(judge(mid)) ans = mid , l = mid + 1;
		else r = mid - 1;
	}
	printf("%d\n" , ans);
	return 0;
}

【bzoj4898】[Apio2017]商旅 Floyd+分数规划+Spfa

标签：再处理 memset namespace turn ... lin 无法 long cstring

原文地址：http://www.cnblogs.com/GXZlegend/p/7570573.html

上一篇：RestSharp Simple REST and HTTP API Client for .NET

下一篇：C#(去、过滤)掉字符中的换行符

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【bzoj4898】[Apio2017]商旅 Floyd+分数规划+Spfa
文章链接：http://soscw.com/index.php/essay/84767.html

亲，登录后才可以留言！

【bzoj4898】[Apio2017]商旅 Floyd+分数规划+Spfa

评论

热门文章

推荐文章

最新文章

置顶文章