H 有趣的网络流

题意

费用网络中每条边的容量均为 $u/v$，输入大小为 1 的流，问最小费用是多少。多次询问不同的 $u/v$。

思路

先特判容量为 0，输出 NaN。

考虑转化网络，容量为 $u/v$ 的边可以看作容量为 1F 的边（F为单位），那么输入大小为 1 的流相当于输入大小为 $v/u$ (F) 的流 由于费用流容量均为一，EK费用流中，每次迭代增加的最大流量均为 1，记录每次迭代中，当前流量与最小费用的关系，可得到流量与最小费用的数组 $ans$

如果边的容量为u/v $\to$ 输入流的大小为 $v/u$ (F)：

  1. 若 $v/u > maxflow$ ，输出 NaN，反之执行 2.
  2. 若 $v/u$ 为整数，直接输出 $ans[v/u] * u/v$ (单位转换)，反之执行 3.
  3. 若 $v/u$ 不为整数，进行插值，并进行单位转化，输出结果

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>

using namespace std;
using ll = long long;

const int N = 55, M = 205;

struct edge {
    int to, w, cost;
} edges[M];

vector<int> out_edges[N];
int vis[N], d[N], flow[N], fa[N], last[N];
int tot;

ll ans[M];

inline void init() {
    tot = 0;
    for (int i = 0; i < N; ++i) 
        out_edges[i].clear(); 
}

inline void add_edge(int u, int v, int w, int cost) {
    edges[tot] = {v, w, cost};
    out_edges[u].emplace_back(tot++);
}


bool spfa(int s, int t) {
    memset(vis, 0, sizeof(vis));
    memset(flow, 0x3f, sizeof(flow));
    memset(d, 0x3f, sizeof(d));
    queue<int> que;
    que.push(s), vis[s] = 1, d[s] = 0, fa[t] = -1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = 0;
        for (int i : out_edges[u]) {
            int v = edges[i].to;
            if(edges[i].w > 0 && d[v] > d[u] + edges[i].cost){
                d[v] = d[u] + edges[i].cost;
                fa[v] = u;
                last[v] = i;
                flow[v] = std::min(flow[u], edges[i].w);
                if(!vis[v]){
                    vis[v] = 1;
                    que.push(v);
                }
            }
        }
    }
    return fa[t] != -1;
}


void mcmf(int s, int t, ll &maxflow, ll &mincost) {
    maxflow = 0, mincost = 0;
    while (spfa(s, t)) {
        int u = t;
        maxflow += flow[t];
        mincost += flow[t] * d[t];
        ans[maxflow] = mincost;
        while(u != s){
            edges[last[u]].w -= flow[t];
            edges[last[u] ^ 1].w += flow[t];
            u = fa[u];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    while(cin >> n >> m){
        init();
        for (int i = 0; i < m; ++i) {
            int u, v, cost;
            cin >> u >> v >> cost;
            add_edge(u, v, 1, cost);
            add_edge(v, u, 0, -cost);
        }
        ll maxflow, mincost;
        mcmf(1, n, maxflow, mincost);
        ans[0] = 0;
        ans[maxflow + 1] = ans[maxflow];

        int q;
        cin >> q;
        while(q--) {
            ll x, y;
            cin >> x >> y;

            if (x == 0 || y > x * maxflow) {
                cout << "NaN\n";
                continue;
            }

            ll p = y / x;

            ll up = ans[p] * x + (y % x) * (ans[p + 1] - ans[p]);
            ll low = y;

            ll temp = __gcd(up, low);
            cout << up / temp << "/" << low / temp << "\n";
        }
    }
    return 0;
}