bzoj 4898: [Apio2017]商旅

Description

在广阔的澳大利亚内陆地区长途跋涉后，你孤身一人带着一个背包来到了科巴。你被这个城市发达而美丽的市场所

深深吸引，决定定居于此，做一个商人。科巴有个集市，集市用从1到N的整数编号，集市之间通过M条单向道路连

接，通过每条道路都需要消耗一定的时间。在科巴的集市上，有K种不同的商品，商品用从1到K的整数编号。每个

集市对每种商品都有自己的定价，买入和卖出商品的价格可以是不同的。并非每个集市都可以买卖所有的商品：一

个集市可能只提供部分商品的双向交易服务；对于一种商品，一个集市也可能只收购而不卖出该商品或只卖出而不

收购该商品。如果一个集市收购一种商品，它收购这种商品的数量是不限的，同样，一个集市如果卖出一种商品，

则它卖出这种商品的数量也是不限的。为了更快地获得收益，你决定寻找一条盈利效率最高的环路。环路是指带着

空的背包从一个集市出发，沿着道路前进，经过若干个市场并最终回到出发点。在环路中，允许多次经过同一个集

市或同一条道路。在经过集市时，你可以购买或者卖出商品，一旦你购买了一个商品，你需要把它装在背包里带走

。由于你的背包非常小，任何时候你最多只能持有一个商品。在购买一个商品时，你不需要考虑你是否有足够的金

钱，但在卖出时，需要注意只能卖出你拥有的商品。从环路中得到的收益为在环路中卖出商品得到的金钱减去购买

商品花费的金钱，而一条环路上消耗的时间则是依次通过环路上所有道路所需要花费的时间的总和。环路的盈利效

率是指从环路中得到的收益除以花费的时间。需要注意的是，一条没有任何交易的环路的盈利效率为0。你需要求

出所有消耗时间为正数的环路中，盈利效率最高的环路的盈利效率。答案向下取整保留到整数。如果没有任何一条

环路可以盈利，则输出0。

Input

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

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

对于任意的1<=j<=k,整数和分别表示在编号为的集市上购买、卖出编号为的商品时的交易价格。

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

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

1<=N<=100,1<=M<=9900

如果在编号为的集市i中，编号为j的商品既可以购买又可以卖出则0<Si,j<=Bi,j<=10^9

对于编号为P(1<=P<=M)的道路，保证Vp<>Wp且1<=Tp<=10^7

不存在满足1<=P<Q<=M的P,Q,使得(Vp,Wp)=(Vq,Wq) 。

Output

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

有任何一条环路可以盈利，则输出0。

Sample Input

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

Sample Output

2
在样例中，我们考虑下面两条环路，“1 - 2 - 3 - 1” 和 “1 - 4 - 3 - 1”。
考虑环路 “1 - 2 - 3 - 1” ：这条环路消耗的总时间是 分钟。在这条环路中，
最佳的交易方式是：在编号为 1 的集市中购买编号为 2 的商品（花费的金钱为 5 ）；在编号
为 2 的集市中卖出编号为 2 的商品（得到的金钱为 15 ），然后立即购买编号为 1 的商品
（花费的金钱为 6 ）；带着编号为 1 的商品经过编号为 3 的集市，在回到编号为 1 的城市后
卖出（得到的金钱为 9 ）。在这个环路中，总盈利为13。 这个环路的
盈利效率为13/7 ，向下取整后为 1 。
考虑环路 “1 - 4 - 3 - 1” ：这条环路消耗的总时间是 分钟。在这条环路中，
最佳的交易方式是：在编号为 1 的集市中购买编号为 2 的商品（花费的金钱为 5 ）；在编号
为 4 的集市中卖出编号为 2 的商品（得到的金钱为 11 ）；然后经过编号为 3 的集市回到编
号为 1 的城市。在这个环路中，总盈利为 6。 这个环路的盈利效率为6/3 ，向
下取整后为 2 。
综上所述，盈利效率最高的环路的盈利效率为 2 。

HINT

Source

鸣谢佚名制作数据

这是apio近几年来最送的一道题了；

首先总收益/总代价明显的就是一道分数规划(这题还是挺良心的，不用实数二分)

对于分数规划，我们要落实到每一步决策上，所以我们重建一个n^2条边的图，图中的每一边都代表一个决策；

我们可以用n^2*k，处理出这n^2个决策，对于点i到点j，决策肯定是买卖最赚钱的那个物品，然后走i-j的最短路，所以每个决策的收益和代价就求出来了；

然后我们用分数规划的套路，二分答案，本来是要判正环的，但是为了复习一下floyd最小环，我反了下符号，变为floyd判是否有负环；

floyd求最小环的原理就是枚举环上编号最大的点，然后更新答案；

//MADE BY QT666

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=105;

int dis[N][N],b[N][N*10],s[N][N*10],n,m,K;

int v[N][N],w[N][N],d[N][N];

bool check(int mid){

    memset(d,127/3,sizeof(d));

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

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

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

	    if(i!=j){

		d[i][j]=min(d[i][j],w[i][j]*mid-v[i][j]);

	    }

	}

    }

    int ret=2147483647;

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

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

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

		ret=min(ret,d[i][k]+d[k][j]+d[j][i]);

	    }

	}

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

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

		d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

	    }

	}

    }

    return ret<=0;

}

int main(){

    scanf("%d%d%d",&n,&m,&K);

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

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

	    scanf("%d%d",&b[i][j],&s[i][j]);

	}

    }

    memset(dis,127/3,sizeof(dis));int l=0,r=0;

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

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

	int x,y,z;scanf("%d%d%d",&x,&y,&z);r=max(r,z);

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

    }

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

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

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

		dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

	    }

	}

    }

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

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

	    if(i!=j){

		int mx=0;

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

		    if(b[i][k]==-1||s[j][k]==-1) continue;

		    mx=max(mx,s[j][k]-b[i][k]);

		}

		v[i][j]=mx;w[i][j]=dis[i][j];

	    }

	}

    }

    int ans=0;

    while(l<=r){

	int mid=(l+r)>>1;

	if(check(mid)) l=mid+1,ans=mid;

	else r=mid-1;

    }

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

    return 0;

}