「APIO2017」商旅
题目描述
在广阔的澳大利亚内陆地区长途跋涉后，你孤身一人带着一个背包来到了科巴。你被这个城市发达而美丽的市场所深深吸引，决定定居于此，做一个商人。科巴有 \(N\) 个集市，集市用从 \(1\) 到 \(N\) 的整数编号，集市之间通过 \(M\) 条 单向 道路连接，通过每条道路都需要消耗一定的时间。
在科巴的集市上，有 \(K\) 种不同的商品，商品用从 \(1\) 到 \(K\) 的整数编号。每个集市对每种商品都有自己的定价，买入和卖出商品的价格可以是不同的。并非每个集市都可以买卖所有的商品：一个集市可能只提供部分商品的双向交易服务；对于一种商品，一个集市也可能只收购而不卖出该商品或只卖出而不收购该商品。如果一个集市收购一种商品，它收购这种商品的数量是不限的，同样，一个集市如果卖出一种商品，则它卖出这种商品的数量也是不限的。
为了更快地获得收益，你决定寻找一条盈利效率最高的环路。环路是指带着空的背包从一个集市出发，沿着道路前进，经过若干个市场并最终回到出发点。在环路中，允许 多次 经过同一个集市或同一条道路。在经过集市时，你可以购买或者卖出商品，一旦你购买了一个商品，你需要把它装在背包里带走。由于你的背包非常小，任何时候你最多只能持有一个商品。在购买一个商品时，你不需要考虑你是否有足够的金钱，但在卖出时，需要注意只能卖出你拥有的商品。
从环路中得到的收益为在环路中卖出商品得到的金钱减去购买商品花费的金钱，而一条环路上消耗的时间则是依次通过环路上所有道路所需要花费的时间的总和。环路的 盈利效率 是指从环路中得到的收益除以花费的时间。需要注意的是，一条没有任何交易的环路的盈利效率为 \(0\) 。
你需要求出所有 消耗时间为正数 的环路中，盈利效率 最高 的环路的盈利效率。答案 向下取整 保留到整数。如果没有任何一条环路可以盈利，则输出 \(0\) 。
输入格式
第一行包含 \(3\) 个正整数，\(N\) , \(M\) 和 \(K\)，分别表示集市数量、道路数量和商品种类数量。
接下来的 \(N\) 行，第 \(i\) 行中包含 \(2K\) 个整数 \(B_{i,1},S_{i,1},B_{i,2},S_{i,2},\cdots ,B_{i,K},S_{i,K}\) 描述一个集市。对于任意的 \(1\leq j\leq K\) ，整数 \(B_{i,j},S_{i,j}\) 分别表示在编号为 \(i\) 的集市上购买、卖出编号为 \(j\) 的商品时的交易价格。如果一个交易价格为 \(-1\)，则表示这个商品在这个集市上不能进行这种交易。
接下来 \(M\) 行，第 \(p\) 行包含 \(3\) 个整数 \(V_p,W_p,T_p\)，表示存在一条从编号为 \(V_p\) 的市场出发前往编号为 \(W_p\) 的市场的路径花费 \(T_p\) 分钟。
输出格式
输出包含一个整数，表示盈利效率最高的环路盈利效率，答案 向下取整 保留到整数。如果没有任何一条环路可以盈利，则输出 \(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
样例输出
2
数据范围与提示
在所有数据中，满足：$ 1\le N \le 100,1\le M \le 9900,1\le K \le 1000$，如果在编号为 \(i (1\le i\le N)\) 的集市中，编号为 \(j(1\le j\le K)\) 的商品既可以购买又可以卖出，则 \(0\le S_{ij}\le B_{ij}\le 10^9\)。
对于编号为 \(p (1\le p\le M)\) 的道路，保证 \(V_p\neq W_p\)，且 \(1\le T_p\le 10^7\)。
不存在满足 \(1\le p\le q\le M\) 的 \(p,q\) 使得 \((V_p,W_p)=(V_q,W_q)\)。
比较容易看出是\(01\)分数规划，然后转为判定性问题。
主要是考虑建图的问题。
我一开始以为要记个二维变量\(dis_{v,u}\)表示到\(v\)，上一个交易的位置在\(u\)的最长路。然后复杂度爆炸。我还是太naive了。
我们设\(mp_{v,u}\)表示\(v\)到\(u\)的最短路，这个可以用\(floyd\)预处理。
我们在预处理在\(i\)购买，在\(j\)卖出的最大收益\(mx_{i,j}\)
然后假设我们二分出的答案为\(ans\)，那我们就连\((i,j,mx_{i,j}-ans\cdot mp_{v,u})\)。然后用\(dfs\)找非负环。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 105
#define M 10005
#define K 1005
#define eps 1e-3
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n,m,k;
ll mp[N][N];
struct road {
int to,next;
ll w;
}s[M];
int h[N],cnt;
void add(int i,int j,ll w) {s[++cnt]=(road) {j,h[i],w};h[i]=cnt;}
ll B[N][K],S[N][K];
ll mx[N][N];
void build(ll ans) {
memset(h,0,sizeof(h));
cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(mp[i][j]<=1e9) {
add(i,j,mx[i][j]-mp[i][j]*ans);
}
}
bool vis[N],ins[N];
ll dis[N];
bool dfs(int v) {
vis[v]=ins[v]=1;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(dis[to]<=dis[v]+s[i].w) {
dis[to]=dis[v]+s[i].w;
if(ins[to]) return 1;
if(dfs(to)) return 1;
}
}
ins[v]=0;
return 0;
}
bool chk(ll ans) {
build(ans);
memset(ins,0,sizeof(ins));
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
for(int i=1;i<=n;i++) {
if(!vis[i]) {
dis[i]=0;
if(dfs(i)) return 1;
}
}
return 0;
}
int main() {
n=Get(),m=Get(),k=Get();
for(int i=1;i<=n;i++) {
for(int j=1;j<=k;j++) {
B[i][j]=Get();
S[i][j]=Get();
}
}
memset(mp,0x3f,sizeof(mp));
for(int i=1;i<=m;i++) {
int a=Get(),b=Get();
mp[a][b]=Get();
}
for(int p=1;p<=n;p++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(mp[i][p]<1e18&&mp[p][j]<1e18) mp[i][j]=min(mp[i][j],mp[i][p]+mp[p][j]);
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
mx[i][j]=0;
for(int q=1;q<=k;q++) {
if(B[i][q]!=-1&&S[j][q]!=-1) {
mx[i][j]=max(mx[i][j],S[j][q]-B[i][q]);
}
}
}
}
ll l=0,r=1e9,mid;
while(l<r) {
mid=l+r+1>>1;
if(!chk(mid)) r=mid-1;
else l=mid;
}
cout<<l;
return 0;
}