• 欢迎光临~

## 题意

(n)个物品，(m)个转换，每(ka_i)(b_i)类物品可以换(w cdot kc_i)(d_i)类物品。其中(k)为任意正实数。

（题目翻译来源于emofunc的讲解PPT）

## 数据范围

(2 leq n leq 1000)
(2 leq m leq 2000)

## 代码

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

const int N = 2010;
const double eps = 1e-8;

int n, m;
int h[N], e[N], ne[N], idx;
double w[N], d[N];
bool st[N];
int cnt[N];

void add(int a, int b, double c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool check(double x)
{
queue<int> que;
for(int i = 1; i <= n; i ++) {
que.push(i);
st[i] = true;
cnt[i] = 0;
d[i] = 0;
}
double k = log(x);
while(que.size()) {
int t = que.front();
que.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if(d[j] > d[t] - w[i] - k) {
d[j] = d[t] - w[i] - k;
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return false;
if(!st[j]) {
st[j] = true;
que.push(j);
}
}
}
}
return true;
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
add(b, d, log(1.0 * c / a));
}
double l = 0.0, r = 1.0;
for(int i = 0; i < 100; i ++) {
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.10fn", l);
return 0;
}
``````