牛客网的效果不太行,建议移步去我的博客看。
这里先贴一份代码
#include <bits/stdc++.h> using namespace std; const int N = 50 + 5, M = 2 * 1000 + 5; const long long Inf = 1e17; using ll = long long; using arr = int[N]; /*-----------------------------------------------------------------*/ int n, m, q, Ecnt, Fi[N]; ll dis[N], f[N]; struct Edge { int nx, v, c, w; } E[M]; inline void Add(int u, int v, int c, int w) { E[++Ecnt] = (Edge){Fi[u], v, c, w}, Fi[u] = Ecnt; } class MCMF { private: static const int N = 2e5 + 5; ll h[N]; int Flow[N], Pre[N], From[N]; struct Seg { int Cnt, tr[N << 2]; inline void Cls() { fill(tr, tr + 2 * Cnt + 1, 0); Cnt = 0; } inline int Cmp(int a, int b) { return dis[a] < dis[b] ? a : b; } inline void Set(int n) { for (Cnt = 1; Cnt < n + 2; Cnt <<= 1) ; tr[0] = n + 1; } inline void Mdy(int u, ll w) { for (int i = u + Cnt; dis[tr[i]] > w; tr[i] = u, i >>= 1) ; dis[u] = w; } inline void Del(int u) { for (tr[u += Cnt] = 0, u >>= 1; u; tr[u] = Cmp(tr[u << 1], tr[u << 1 | 1]), u >>= 1) ; } } zkw; inline bool Dij(int n, int S, int T) { for (int i = 0; i <= n; ++i) dis[i] = Inf, Flow[i] = From[i] = Pre[i] = 0; Flow[S] = 1e9; dis[n + 1] = 0; zkw.Cls(), zkw.Set(n); zkw.Mdy(S, 0); for (int _ = 2; _ <= n; ++_) { int u = zkw.tr[1]; zkw.Del(u); for (int i = Fi[u], v = E[i].v; i; v = E[i = E[i].nx].v) if (E[i].c > 0 && dis[v] > dis[u] + E[i].w + h[u] - h[v]) { zkw.Mdy(v, dis[u] + E[i].w + h[u] - h[v]); From[v] = u, Pre[v] = i; Flow[v] = min(Flow[u], E[i].c); } } return dis[T] != Inf; } public: int MF; inline void Calc(int n, int S, int T) { int Now; for (int i = 1; i <= n; ++i) h[i] = 0; while (Dij(n, S, T)) { MF += (Now = Flow[T]); f[MF] = f[MF - Now] + Now * (dis[T] - h[S] + h[T]); for (int v = T; v != S; v = From[v]) E[Pre[v]].c -= Now, E[Pre[v] ^ 1].c += Now; for (int i = 1; i <= n; ++i) h[i] += dis[i]; } } } D; inline void CLS() { Ecnt = 1; D.MF = 0; for (int i = 1; i <= n; ++i) Fi[i] = f[i] = 0; } inline void Solve() { CLS(); for (int u, v, w; m--;) { scanf("%d%d%d", &u, &v, &w); Add(u, v, 1, w), Add(v, u, 0, -w); } D.Calc(n, 1, n); scanf("%d", &q); for (ll u, v, k; q--;) { scanf("%lld%lld", &u, &v); if (u == 0 || (k = v / u) > D.MF || (v - u * k > 0 && !f[k + 1])) puts("NaN"); else { ll a = (v - k * u) * (f[k + 1] - f[k]) + u * f[k], b = v, g = __gcd(a, b); printf("%lld/%lld\n", a / g, b / g); } } } int main() { while (~scanf("%d%d", &n, &m)) Solve(); return 0; }