题解

由于所有边的容量相同，所以可以得到一个性质，的流量在图中形成了k条1-n的路径，每多u的流量多形成一条路径（可能会导致原路径改变，但是只会在到时发生改变），这u的流量所用的花费是相同的，所以考虑u和v的倍数关系，预处理出u为1，v从1到100的花费，然后询问时直接求出对应的花费

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
struct ZKW_SPFA{
    #define maxn 201
    #define maxe 5005
    const ll INF=1e18;
    ll dis[maxn],vis[maxn],head[maxn],tot;
    ll n,Cost=0,Flow=0;
    struct Edge{ll v,cap,cost,nxt;}g[maxe<<1];
    void init(ll _n){tot=Cost=Flow=0;memset(head,-1,sizeof(head));n=_n;}
    void add(ll u,ll v,ll cap,ll cost){
        g[tot]={v,cap,cost,head[u]};head[u]=tot++;
    }
    void addedge(ll u,ll v,ll cap,ll cost){
        add(u,v,cap,cost);add(v,u,0,-cost);
    }
    bool spfa(ll S,ll T){
        for(ll i=0;i<=n;i++) vis[i]=0,dis[i]=INF;
        deque<ll>Q;Q.push_back(T);dis[T]=0;vis[T]=1;
        while(!Q.empty()){
            ll u=Q.front();Q.pop_front();
            for(ll i=head[u],v;~i;i=g[i].nxt)
                if(g[i^1].cap&&dis[v=g[i].v]>dis[u]+g[i^1].cost){
                    dis[v]=dis[u]+g[i^1].cost;
                    if(!vis[v]){
                        vis[v]=1;
                        if(!Q.empty()&&dis[v]<dis[Q.front()]) Q.push_front(v);
                        else Q.push_back(v);
                        //SLF???
                    }
                } vis[u]=0;
        } return dis[S]<INF;
    }
    ll dfs(ll S,ll T,ll flow){
        if(S==T){vis[T]=1;return flow;}
        ll used=0,res;vis[S]=1;
        for(ll i=head[S],v;~i;i=g[i].nxt)
            if(!vis[v=g[i].v]&&g[i].cap&&dis[S]-g[i].cost==dis[v]){
                res=dfs(v,T,min(g[i].cap,flow-used));
                if(res) Cost+=res*g[i].cost,g[i].cap-=res,g[i^1].cap+=res,used+=res;
                if(used==flow)break;
            }
        return used;
    }
    void solve(ll S,ll T){
        while(spfa(S,T)){
            vis[T]=1;
            while(vis[T]) memset(vis,0,sizeof vis),Flow+=dfs(S,T,INF);
        }
    }
    //?zkw.init(n),?zkw.addedge(),?zkw.solve(S,T)
    //????zkw.Flow??kw.Cost
}zkw;
ll ans[105];
ll x[105],y[105],z[105];
void work()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        zkw.init(n+2);
        for(int i=1;i<=m;i++){
            scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
        }
        int limit=0;
        for(int i=1;i<=101;i++){
            zkw.init(n+2);
            zkw.addedge(n+1,1,i,0);
            for(int j=1;j<=m;j++){
                zkw.addedge(x[j],y[j],1,z[j]);
            }
            zkw.solve(n+1,n);
            ans[i]=zkw.Cost;
            if(zkw.Flow!=i){
                limit=i-1;break;
            }
        }
        int q;
        scanf("%d",&q);
        while(q--){
            ll u,v;
            scanf("%lld%lld",&u,&v);
            if(u*limit<v){
                printf("NaN\n");continue;
            }
            ll sum=ans[v/u]*u;
            ll tmp=v%u;
            sum+=(ans[v/u+1]-ans[v/u])*tmp;
            ll tmp1=__gcd(sum,v);
            sum/=tmp1;
            v/=tmp1;
            printf("%lld/%lld\n",sum,v);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}