# 题目

https://ac.nowcoder.com/acm/contest/33187/D

①二分答案+SPFA判负环

②Karp的最小平均权重环路算法

# 题解

${a}_{i}×{b}_{i}\to {c}_{i}×{d}_{i}a_i\times b_i\to c_i \times d_i$

$\frac{{a}_{i}}{{c}_{i}}×{b}_{i}\to {d}_{i}\frac\left\{a_i\right\}\left\{c_i\right\}\times b_i \to d_i$

$\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}\mathrm{原}\mathrm{料}\to \mathrm{产}\mathrm{品}\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\} 原料\to 产品$

$\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}\mathrm{物}\mathrm{品}\to \mathrm{物}\mathrm{品}\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\} 物品\to 物品$

$nn$种物品为点, $mm$种配方为边, $\frac{{a}_{i}}{{c}_{i}}\frac\left\{a_i\right\}\left\{c_i\right\}$为边权建立有向图, 循环配方表现为环

$\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}\ge 1\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\}\ge 1$

${a}_{i}×{b}_{i}\to w×{c}_{i}×{d}_{i}a_i\times b_i\to w\times c_i \times d_i$

$\frac{{a}_{i}}{w{c}_{i}}×{b}_{i}\to {d}_{i}\frac\left\{a_i\right\}\left\{wc_i\right\}\times b_i \to d_i$

$\prod _{i}^{k}\frac{{a}_{i}}{w{c}_{i}}\mathrm{物}\mathrm{品}\to \mathrm{物}\mathrm{品}\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{wc_i\right\} 物品\to 物品$

$ww$提出有

$\frac{1}{{w}^{k}}\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}\mathrm{物}\mathrm{品}\to \mathrm{物}\mathrm{品}\frac1\left\{w^k\right\}\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\} 物品\to 物品$

$nn$种物品为点, $mm$种配方为边, $\frac{{a}_{i}}{w{c}_{i}}\frac\left\{a_i\right\}\left\{wc_i\right\}$为边权建立有向图, 循环配方表现为环

$\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}\ge {w}^{k}\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\}\ge w^k$

$\mathrm{min}\left(\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}\right)\ge {w}^{k}\min\left(\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\}\right)\ge w^k$

$\mathrm{min}\left(\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}\right)={w}^{k}\min\left(\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\}\right)=w^k$

$w=\mathrm{min}\left(\sqrt[k]{\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}}\right)w=\min\left\left(\sqrt\left[k\right]\left\{\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\}\right\}\right\right)$

$\mathrm{ln}\left(\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}\right)=\sum _{i}^{k}\mathrm{ln}\left(\frac{{a}_{i}}{{c}_{i}}\right)\ln\left(\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\}\right)=\sum_i^k\ln\left(\frac\left\{a_i\right\}\left\{c_i\right\}\right)$

$\prod _{i}^{k}\frac{{a}_{i}}{{c}_{i}}={e}^{\sum _{i}^{k}\mathrm{ln}\left(\frac{{a}_{i}}{{c}_{i}}\right)}\prod_\left\{i\right\}^k\frac\left\{a_i\right\}\left\{c_i\right\}=e^\left\{\sum_i^k\ln\left(\frac\left\{a_i\right\}\left\{c_i\right\}\right)\right\}$

${w}^{k}={e}^{\mathrm{min}\left(\sum _{i}^{k}\mathrm{ln}\left(\frac{{a}_{i}}{{c}_{i}}\right)\right)}w^k=e^\left\{\min\left(\sum_i^k\ln\left(\frac\left\{a_i\right\}\left\{c_i\right\}\right)\right)\right\}$

$w=\mathrm{min}\left(\sqrt[k]{{e}^{\sum _{i}^{k}\mathrm{ln}\left(\frac{{a}_{i}}{{c}_{i}}\right)}}\right)w=\min\left(\sqrt\left[k\right]\left\{e^\left\{\sum_i^k\ln\left(\frac\left\{a_i\right\}\left\{c_i\right\}\right)\right\}\right\}\right)$
$w=\mathrm{exp}\left(\mathrm{min}\left(\frac{\sum _{i}^{k}\mathrm{ln}\left(\frac{{a}_{i}}{{c}_{i}}\right)}{k}\right)\right)w=\exp\left\left(\min\left(\frac\left\{\sum_i^k\ln\left(\frac\left\{a_i\right\}\left\{c_i\right\}\right)\right\}\left\{k\right\}\right)\right\right)$

$\mathrm{ln}\left(\frac{{a}_{i}}{{c}_{i}}\right)\ln\left(\frac\left\{a_i\right\}\left\{c_i\right\}\right)$为边权建图$G\left(V,E\right)G\left(V,E\right)$

$Karp\mathrm{的}\mathrm{最}\mathrm{小}\mathrm{平}\mathrm{均}\mathrm{权}\mathrm{重}\mathrm{环}\mathrm{路}\mathrm{算}\mathrm{法}Karp的最小平均权重环路算法$

$F\left[k\right]\left[v\right]F\left[k\right]\left[v\right]$为从任意点出发,经过$kk$条边到达$vv$点的最短距离, 对每条边$u\to vu\to v$

$F\left[k\right]\left[v\right]=\underset{e\in E}{}\left\{F\left[k-1\right]\left[u\right]+w\left[u\right]\left[v\right]\right\}F\left[k\right]\left[v\right]=\min_\left\{e\in E\right\}\\left\{F\left[k-1\right]\left[u\right]+w\left[u\right]\left[v\right]\\right\}$
$ans=\underset{v\in V}{}\left\{\underset{0\le k\le n-1}{}\left\{\frac{F\left[n\right]\left[v\right]-F\left[k\right]\left[v\right]}{n-k}\right\}\right\}ans = \min_\left\{v\in V\right\}\\left\{\max_\left\{0\le k\le n-1\right\}\\left\{\frac\left\{F\left[n\right]\left[v\right]-F\left[k\right]\left[v\right]\right\}\left\{n-k\right\}\\right\}\\right\}$

# 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2005;
int n,m,b,d;
double a,c,ans;
double dp[maxn][maxn];
struct edge {
int u;
int v;
double w;
};
vector<edge> edges;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a>>b>>c>>d;
edges.push_back({b,d,log(a/c)});
}
for (int i=1;i<=n;i++) {
for (auto [u,v,w] : edges) {
dp[i][v] = min(dp[i][v],dp[i-1][u]+w);
}
}
for(int i=1;i<=n;i++){
double t = -INFINITY;
for(int j=0;j<n;j++){
double dis = (dp[n][i]-dp[j][i]);
int k = (n-j);
t = max(t,dis/k);
}
ans = min(t,ans);
}
printf("%.15lf\n",exp(ans));
return 0;
}