题解
分数题可以想到分数规划，我们预处理出从i到j卖什么货物赚的最多，然后把每条边的边权改成“利润 - 效率 × 时间”
用spfa找正环即可
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define MAXN 300005
#define mo 994711
#define eps 1e-8
//#define ivorysi
using namespace std;
typedef long long int64;
typedef long double db;
typedef unsigned int u32;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
int N,M,K;
int64 g[105][105],h[105][105],inf = 1e14;
int64 B[105][1005],S[105][1005],dis[105];
bool vis[105],mark[105];
struct node {
int to,next;int64 val;
}E[20005];
int head[105],sumE;
void add(int u,int v,int64 c) {
E[++sumE].to = v;
E[sumE].next = head[u];
E[sumE].val = c;
head[u] = sumE;
}
bool SPFA_dfs(int u) {
vis[u] = 1;
mark[u] = 1;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(dis[v] <= dis[u] + E[i].val) {
dis[v] = dis[u] + E[i].val;
if(vis[v]) return false;
if(!SPFA_dfs(v)) return false;
}
}
vis[u] = 0;
return true;
}
bool check(int64 mid) {
memset(head,0,sizeof(head));sumE = 0;
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
if(g[i][j] < inf) add(i,j,h[i][j] - g[i][j] * mid);
}
}
memset(vis,0,sizeof(vis));memset(mark,0,sizeof(mark));
for(int i = 1 ; i <= N ; ++i) dis[i] = 0;
for(int i = 1 ; i <= N ; ++i) {
if(!mark[i]) {
if(!SPFA_dfs(i)) return true;
}
}
return false;
}
void Solve() {
read(N);read(M);read(K);
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
g[i][j] = inf;
}
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= K ; ++j) {
read(B[i][j]);read(S[i][j]);
}
}
int v,w;int64 t;
for(int i = 1 ; i <= M ; ++i) {
read(v);read(w);read(t);
g[v][w] = t;
}
for(int k = 1 ; k <= N ; ++k) {
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
g[i][j] = min(g[i][j],g[i][k] + g[k][j]);
}
}
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
for(int k = 1 ; k <= K ; ++k) {
if(B[i][k] != -1 && S[j][k] != -1) h[i][j] = max(S[j][k] - B[i][k],h[i][j]);
}
}
}
int64 L = 0,R = 1e9;
while(L < R) {
int64 mid = (L + R + 1) >> 1;
if(check(mid)) L = mid;
else R = mid - 1;
}
out(L);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}