Milk Pumping (USACO Gold 2019 December)

这是最短路的有一定灵活性的一个应用。

题目要我们计算从节点1到节点n的flow/cost的最大值，首先这个看起来和最短路还是有关系的，不考虑flow的情况下，就是一个最短路问题，但困难在于在算最短路的过程中间，还要考虑一个除法关系的flow值，会比较麻烦。

一条思路就是重新实现一个考虑flow的最短路算法，其实就是一个DP， $dp[i][j]$ 是到 $i$ 节点，最小flow是 $j$ 的时候的最短路，这个应该是可以的，因为flow最大值只有 $1000$ 。

我们可以实现这个DP，或者再往下想一步，能有一个更直观一些的方法：因为flow是一个全局的属性（只有路径上最小值才起做用），可以想到如下全局性的迭代方法。我们可以修改图，按flow从大往小一条条加边，然后反复跑Dijkstra，这样其实效果和上面的DP是一样的，但只需要标准Dijkstra就可以了。复杂度 $\mathcal{O}(m^2 \log n)$ 。

另外一种实现方法，也可以在Dijkstra中检查flow是否大于一个值，这样不用修改图。

注意，Dijkstra中continue那一行是重要的，否则一个节点会被展开多次，复杂度过高。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m;
struct E {
    int a,b,c,f;
};
E es[1005];
bool cmp(E &a, E &b) {return a.f > b.f; }
vector<pair<int,int>> adj[1005];        // target, cost
double ans = 0;
int dist[1005];     // shortest distance from 0
 
void dijkstra() {
    fill(dist, dist+n, 1e9);
    dist[0] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    q.push({0,0});
    while (!q.empty()) {
        int x = q.top().first, dx=q.top().second;
        q.pop();
        if (dx != dist[x]) continue;        // make sure every vertex is used to relax only once 
        for (auto p: adj[x]) {
            int y = p.first, dy = p.second;
            if (dist[x] + dy < dist[y]) {
                dist[y] = dist[x] + dy;
                q.push({y,dist[y]});
            }
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d %d", &es[i].a, &es[i].b, &es[i].c, &es[i].f);
        es[i].a--; es[i].b--;        
    }
    sort(es, es+m, cmp);        // decreasing flow
 
    for (int i = 0; i < m; i++) {
        adj[es[i].a].push_back({es[i].b, es[i].c});
        adj[es[i].b].push_back({es[i].a, es[i].c});
        dijkstra();
        ans = max(ans, (double)es[i].f / dist[n-1]);
    }
 
    printf("%d", (int)(ans*1000000));
 
    return 0;
}