题目链接：https://ac.nowcoder.com/acm/contest/5666/H
题意：给你一个n个点m条边的图，q次询问每次给出u和v，每条边的容量都为u/v， 初始流量为1，询问满流时候的最小费用。
首先将每条边的容量设为1跑一遍费用流 。那么对于某次询问容量变为u/v，只要将起始流量设为v，每条边容量设为u之后得到的答案再除回v即可。
而如何实现上述操作，只要先预处理出容量为1时每次求增广路所需要的花费，然后优先选花费最小的v/u(向上整除)条增广路，如果v%u!=0,
那么最后一条增广路上的容量应该是v%u而不是u。这样子q次询问的答案，全部可以通过一开始容量为1的费用流得出的结果线性表示。具体实现见代码。
#include<bits/stdc++.h> #define ll long long #define PB push_back #define endl '\n' #define INF 0x3f3f3f3f #define LINF 0x3f3f3f3f3f3f3f3f #define ull unsigned long long #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define lowbit(x) (x & (-x)) #define rep(i, a, b) for(int i = a ; i <= b ; ++ i) #define per(i, a, b) for(int i = b ; i >= a ; -- i) #define clr(a, b) memset(a, b, sizeof(a)) #define in insert #define random(x) (rand()%x) #define PII(x, y) make_pair(x, y) #define fi first #define se second #define pi acos(-1) using namespace std; const int maxn = 2e6 + 1000; const ll mod = 998244353; const int M = 100 + 10; const int N = 50 + 10; int n, m, s, t, cnt; int head[N], vis[N], inq[N], cur[N]; ll dis[N], sum[M<<1]; ll maxflow, cost; vector<ll> path; struct node{ int to, next; ll cost, flow; }edge[M<<1]; void add(int u, int v, int cost, int flow){ edge[cnt].to = v; edge[cnt].cost = cost; edge[cnt].flow = flow; edge[cnt].next = head[u]; head[u] = cnt ++; } bool spfa(){ rep(i, 1, n) dis[i] = 1e18, inq[i] = 0, cur[i] = head[i]; queue<int> que; dis[s] = 0; inq[s] = 1; que.push(s); while(!que.empty()){ int u = que.front(); que.pop(); inq[u] = 0; for(int i = head[u] ; ~ i ; i = edge[i].next){ int v = edge[i].to; if(dis[v] > dis[u] + edge[i].cost && edge[i].flow){ dis[v] = dis[u] + edge[i].cost; if(!inq[v]){ inq[v] = 1; que.push(v); } } } } return dis[t] == 1e18 ? 0 : 1; } ll dfs(int u, ll flow){ if(u == t){ vis[t] = 1; maxflow += flow; return flow; } ll used = 0; vis[u] = 1; for(int i = cur[u] ; ~ i ; i = edge[i].next){ int v = edge[i].to; cur[u] = i; if((v == t || !vis[v]) && edge[i].flow && dis[v] == dis[u] + edge[i].cost){ ll minflow = dfs(v, min(flow - used, edge[i].flow)); if(minflow){ cost += minflow * edge[i].cost; edge[i].flow -= minflow; edge[i^1].flow += minflow; used += minflow; } if(used == flow) break; } } return used; } void dinic(){ while(spfa()){ vis[t] = 1; path.PB(dis[t]); while(vis[t]){ clr(vis, 0); dfs(s, 1e18); } } } signed main(){ ll u, v, w; int q; while(~scanf("%d %d", &n, &m)){ clr(head, -1); clr(vis, 0); path.clear(); maxflow = cost = 0; s = 1; t = n; cnt = 0; while(m --){ scanf("%lld %lld %lld", &u, &v, &w); add(u, v, w, 1); add(v, u, -w, 0); } scanf("%d", &q); dinic(); ll sz = path.size(); rep(i, 0, sz-1) sum[i+1] = sum[i] + path[i]; while(q --){ scanf("%lld %lld", &u, &v); if(sz * u < v) {puts("NaN"); continue;} ll x = v / u, y = v % u; ll ans = sum[x] * u + path[x] * y; ll tmp = __gcd(ans, v); cout << ans / tmp << '/' << v / tmp << endl; } } return 0; }