Topic link: https://ac.nowcoder.com/acm/contest/5666/H

meaning of the title

Give you a directed graph of n vertices, m edges, and give the cost of each edge. Then q queries are performed, each query gives the capacity of each edge (expressed as a fraction), and the capacity of all edges is equal. For each query, you need to output the minimum fee (in fractional representation) from point 1 to point n when the total flow is 1.

ideas

The difficulty of this question lies in the multiple inquiries, and q reaches 1e5, so if you build a map and run the cost flow for each inquiry, it will definitely time out.

Then you might as well run the cost flow once before the query to get some useful information, so that each subsequent query can try to achieve O(1) complexity (in fact, there is no O(1), because fraction reduction requires gcd, requires O(logn) complexity).

For each query, the total flow is 1 and each edge capacity is u/v. Considering scaling and multiplying by v at the same time, the total flow is v, and the capacity of each edge is u. At this time, the calculated total cost divided by v is the answer. We can pre-process to get the cost of all augmented paths before querying. After each SPFA algorithm is performed, we can get the cost of an augmented path and record it in the path array (according to the augmentation order, each path can be guaranteed The augmented road cost is in ascending order), and its prefix sum is obtained to facilitate the processing of subsequent queries.

Before querying, preprocess to get:
(1) path[a], indicating the cost of the a+1 augmented path when the unit capacity (traffic is full, traffic = capacity).
(2) sum[a], indicating the total cost of the previous a augmentation path when the unit capacity (traffic is full, traffic = capacity).

Each query is processed next.
Assume that v=a*u+b (b<u), that is, the flow of the first a widening road is u, and the flow of the first a+1 widening road is less than u, and the flow is B
Since sum and path are the cost of the unit capacity obtained from the previous preprocessing, sum[a] needs to be multiplied by u to obtain the total cost of the augmented road a before when the flow is u, and path[a] needs to be multiplied by b to obtain the flow When b is the a+1 augmented path cost, then ans=(sum[a]*u+path[a]*b)/v.

AC code

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1010,M=1010,inf=(1ll<<63)-1;
ll n,m,s,t,cnt,mincost,head[N],dis[N],vis[N],cur[N],sum[M];
vector<ll>path;
struct edge
{
    ll to,next,cap,cost;//cap is the capacity, cost is the cost per unit of traffic
}e[M<<1];
void add(ll x,ll y,ll z,ll c)
{
    e[cnt].to=y;
    e[cnt].cap=z;
    e[cnt].cost=c;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(ll x,ll y,ll z,ll c)
{
    add(x,y,z,c);
    add(y,x,0,-c);//The reverse edge capacity is 0, and the cost per unit flow is -c
}
bool spfa()
{
    queue<int>q;
    for(ll i=1;i<=n;i++)
        dis[i]=inf;
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;//enqueue marker
    q.push(s);
    while(!q.empty())
    {
        ll u=q.front();q.pop();
        vis[u]=0;//Dequeue mark
        for(ll i=head[u];i!=-1;i=e[i].next)
        {
            ll v=e[i].to;
            if(e[i].cap>0&&dis[u]+e[i].cost<dis[v])
            {
                dis[v]=dis[u]+e[i].cost;
                if(!vis[v])
                {
                    vis[v]=1;//enqueue marker
                    q.push(v);
                }
            }
        }
    }//When the queue is empty, vis is also all set to 0
    if(dis[t]!=inf)return 1;
    return 0;
}
ll dfs(ll u,ll flow)
{
    vis[u]=1;//Pay attention to mark the points passed by vis to prevent infinite loops
    if(u==t)return flow;//Reach the sink and return the minimum flow on this augmented path
    for(ll& i=cur[u];i!=-1;i=e[i].next)
    {
        ll v=e[i].to;
        if(e[i].cap>0&&dis[v]==dis[u]+e[i].cost&&!vis[v])
        {
            ll di=dfs(v,min(flow,e[i].cap));//min(flow,e[i].w) represents the minimum flow from the starting point to v
            if(di>0)//Prevent the dfs result from returning 0, if di=0, it will loop infinitely
            {
                e[i].cap-=di;
                e[i^1].cap+=di;//add di on the reverse side
                mincost+=di*e[i].cost;
                return di;//di represents the minimum flow on the entire augmented road. When backtracking, it always returns upwards, and the returned di is unchanged.
            }
        }
    }
    vis[u]=0;//Restore marked points
    return 0;//Can't find the augmenting road, can't reach the meeting point
}
ll dinic()
{
    ll maxflow=0;
    path.clear();
    while(spfa())//First spfa performs "path exploration" and layering, and then performs multiple dfs after layering
    {
        path.push_back(dis[t]); // The cost of getting an augmented path after each spfa
        memcpy(cur,head,sizeof(head));
        while(ll d=dfs(s,inf))//The meaning of the while loop: as long as dfs is not 0, keep dfs until no augmentation path is found
            maxflow+=d;
    }
    return maxflow;
}
// The above are all templates of the dinic algorithm, but the path array is added, and dis[t] is recorded after each spfa.

int main()
{
    ios::sync_with_stdio(false);
    ll x,y,c,q,u,v;
    while(cin>>n>>m)
    {
        s=1,t=n;
        memset(head,-1,sizeof(head));
        cnt=0;
        mincost=0;
        for(ll i=1;i<=m;i++)
        {
            cin>>x>>y>>c;  // point, edge, cost
            add_edge(x,y,1,c); // Set each edge capacity to 1
        }
        dinic(); // Run the cost flow, and get the cost of each augmented path (from small to large) when the path array records the unit capacity.
        ll pnum=path.size(); // The number of augmented paths
        for(ll i=0;i<pnum;i++)
            sum[i+1]=sum[i]+path[i]; // path[i] is the i+1 augmented path cost
        // Before querying, preprocess to get:
        // sum[a], indicating the total cost of the previous a augmented road when the unit capacity (traffic is full, traffic = capacity)
        // path[a], indicating the cost of the a+1 augmented road when the unit capacity (traffic is full, traffic = capacity)
        cin>>q;
        while(q--)
        {
            cin>>u>>v;
            // The capacity of each augmented path is expanded from u/v to u, the total traffic is expanded from 1 to v, and the final cost is divided by v.
            if(u*pnum<v)printf("NaN\n"); // Capacity < total flow
            else
            {
                // Assume that: v=a*u+b (b<u), that is, the flow of the first a widening road is u, and the flow of the first a+1 widening road is less than u, and the flow is B
                ll a=v/u;
                ll b=v%u;
                // Since the sum and path are the cost of the unit capacity obtained by the previous preprocessing
                // So sum[a] needs to be multiplied by u to get the total cost of the first augmented road a when the flow is u,
                // path[a] needs to be multiplied by b to get the cost of the a+1 augmented road when the flow is b
                ll ans=sum[a]*u+path[a]*b;
                ll k=__gcd(ans,v);
                ans/=k;
                v/=k;
                printf("%lld/%lld\n",ans,v);
            }
        }
    }
    return 0;
}
/*
2 2
1 2 1
1 2 2
3
1 2
2 3
1 4

3 4
1 2 1
1 2 2
2 3 2
2 3 1
*/