Minimum-cost Flow – MCMF – 容量为分数时的处理

传送门
给出一个无向图，已知连接情况和每条边上的费用。
先给出q个查询，每次查询规定了每条边的容量都为\(\frac{u_i}{v_i}\)，求出每次查询时，从源点1到汇点n，流量为1的最小费用值

因为容量一样，那么每个增广路的流量都是\(\frac{u_i}{v_i}\)，也就是说需要\(\frac{v_i}{u_i}\)条增广路，才能使得总流量为1
考虑扩大容量，把容量变成1，也就是说变成了原来的\(\frac{v_i}{u_i}\)倍，那么用vector记录每条增广路的费用，
如果说vec.size() < \(\frac{v_i}{u_i}\)，那么也就是说无法满足。
用前缀和记录下vector里的值，因为此时每次增广路流量为1，那么此时sum[i]就表示流量为i时的最小费用
因为流量是原来\(\frac{v_i}{u_i}\)倍，那么费用应该要乘以\(\frac{u_i}{v_i}\)
也就是说有\(a = \lfloor\frac{v_i}{u_i}\rfloor\)条增广路，以及\(b = v_i % u_i\)，是单独一条增广路的容量，即前面分配剩余的
那么\(\frac{u_i}{v_i} * (a + \frac{1}{b}) = 1\)
可以和样例一起，从而推导出公式

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define ll long long
using namespace std;
const int N = 5e3 + 5;
const int M = 5e4 + 5;
std::vector<int> vec;
struct MCMF{
    struct Edge{
        int to, next, cap, cost; //cap容量， cost单位费用
    }e[M << 1];
    int head[N], tot, n; 
    // dis[] 从源点到各点的最小费用, flow[] 从源点到各点的最小流量, pre[]为每个点的前驱，lats[]为每个点所连的前一个边
    int dis[N], pre[N], last[N], flow[N];
    bool vis[N];
    void init(int n){
        this->n = n; tot = 1;
        memset(head, 0, sizeof(head));
    }
    void add(int u, int v, int cap, int cost){
        e[++tot].to = v;
        e[tot].cap = cap;
        e[tot].cost = cost;
        e[tot].next = head[u];
        head[u] = tot;
    }
    bool spfa(int s, int t){
        queue <int> q;
        memset(dis, 0x7f, sizeof(dis));
        memset(flow, 0x7f, sizeof(flow));
        memset(vis, 0, sizeof(vis));
        q.push(s); vis[s] = 1; dis[s] = 0; pre[t] = -1;

        while (!q.empty()){
            int now = q.front();
            q.pop();
            vis[now] = 0;
            for (int i = head[now]; i; i = e[i].next){
                int v = e[i].to;
                if (e[i].cap > 0 && dis[v] > dis[now] + e[i].cost){
                    dis[v] = dis[now] + e[i].cost;
                    pre[v] = now;
                    last[v] = i;
                    flow[v] = min(flow[now], e[i].cap);
                    if (!vis[v]){
                        vis[e[i].to] = 1;
                        q.push(e[i].to);
                    }
                }
            }
        }
        return pre[t] != -1;
    }
    pair<int,int> mcmf(int s, int t){
        int mincost = 0, maxflow = 0;
        while (spfa(s, t)){ //寻找增广路
            vec.push_back(dis[t]);
            int now = t;
            maxflow += flow[t];
            mincost += flow[t] * dis[t]; // s到t的最小总费用乘以最小流量
            while (now != s){ //从源点一直回溯到汇点 
                e[last[now]].cap -= flow[t]; // 正向流量减少 
                e[last[now] ^ 1].cap += flow[t]; // 反向流量增加
                now = pre[now];
            }
        }
        return make_pair(mincost, maxflow);
    }
} G;
ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a % b);
}
ll sum[N];
int main(){
    int n, m, s, t;
    while(~scanf("%d%d", &n, &m)){
        G.init(n);
        for (int i = 1; i <= m; i++){
            int u, v, cost;
            scanf("%d%d%d", &u, &v, &cost);
            G.add(u, v, 1, cost); G.add(v, u, 0, -cost); // 建立反向边，容量为0，负花费 
        }
        vec.clear();
        G.mcmf(1, n);
        sum[0] = 0;
        for(int i = 0; i < vec.size(); i++) {
            sum[i + 1] = sum[i] + vec[i];
        }
        int q;
        scanf("%d", &q);
        while(q--){
            int u, v;
            scanf("%d%d", &u, &v);
            int a = v / u, b = v % u;
            if(1ll * u * vec.size() < v) {
                printf("NaN\n"); continue;
            }
            ll ans = u * sum[a] + 1ll * vec[a] * b;
            ll d = gcd(ans, 1ll * v);
            printf("%lld/%lld\n", ans / d, v / d);
        }
    }
    return 0;
}