题目链接：点击查看

题目大意：给出一张有向图，每条边都有单独的花费，现在给出 q 次询问，每次询问给出一个 u 和 v 需要回答：将所有边的流量都设置为 u / v 后，从点 1 到点 n 流量为 1 时的最小花费为多少

题目分析：因为询问非常多，肯定不能对于每次询问重新建边，但因为总的边数非常小，所以我们利用等比例的特性，初始时先将每条边的流量都设置为 1 ，在求最小费用最大流的时候，记录一下每个流量下的最小花费，这样对于每次询问，就可以贪心求解了

因为初始时每条边的流量为 1 ，每次询问时每条边的流量为 u / v ，每次询问时的总流量为 1 ，设初始时对应的流量为 x ，根据比例公式不难求解出需要在初始的图中使用 v / u 的流量进行对应，贪心的话选前 v / u 的流量所对应的权值和就好了

代码：
 

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
using namespace std;

typedef long long LL;

typedef unsigned long long ull;

const int inf=0x3f3f3f3f;

const int N=210;

vector<LL>node,sum;

struct Edge
{
	int to,w,cost,next;
}edge[N*N];
 
int head[N],cnt;
 
void addedge(int u,int v,int w,int cost)
{
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].cost=cost;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	edge[cnt].to=u;
	edge[cnt].w=0;
	edge[cnt].cost=-cost;
	edge[cnt].next=head[v];
	head[v]=cnt++;
}
 
int d[N],incf[N],pre[N];
 
bool vis[N];
 
bool spfa(int s,int t)
{
	memset(d,inf,sizeof(d));
	memset(vis,false,sizeof(vis));
    memset(pre,-1,sizeof(pre));
	queue<int>q;
	q.push(s);
	vis[s]=true;
	incf[s]=inf;
	d[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			int cost=edge[i].cost;
			if(!w)
				continue;
			if(d[v]>d[u]+cost)
			{
				d[v]=d[u]+cost;
				pre[v]=i;
				incf[v]=min(incf[u],w);
				if(!vis[v])
				{
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
	return pre[t]!=-1;
}
 
int update(int s,int t)
{
	int x=t;
	while(x!=s)
	{
		int i=pre[x];
		edge[i].w-=incf[t];
		edge[i^1].w+=incf[t];
		node.back()+=edge[i].cost;
		x=edge[i^1].to;
	}
	return d[t]*incf[t];
}
 
void init()
{
	node.clear();
	sum.clear();
	memset(head,-1,sizeof(head));
	cnt=0;
}
 
int solve(int st,int ed)
{
	int ans=0;
	while(spfa(st,ed))
	{
		node.push_back(0);
		update(st,ed);
		ans++;
	}
	return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	int n,m,st=N-1,ed=st-1;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		while(m--)
		{
			int u,v,c;
			scanf("%d%d%d",&u,&v,&c);
			addedge(u,v,1,c);
		}
		addedge(st,1,inf,0);
		addedge(n,ed,inf,0);
		int max_flow=solve(st,ed);
		sum.push_back(0);
		for(int i=0;i<node.size();i++)
			sum.push_back(sum.back()+node[i]);
		int q;
		scanf("%d",&q);
		while(q--)
		{
			LL u,v;
			scanf("%lld%lld",&u,&v);
			if(u*max_flow<v)
			{
				puts("NaN");
				continue;
			}
			int j=v/u;
			LL ans1=sum[j]*u+(sum[j+1]-sum[j])*(v-j*u);
			LL ans2=v;
			LL gcd=__gcd(ans1,ans2);
			ans1/=gcd;
			ans2/=gcd;
			printf("%lld/%lld\n",ans1,ans2);
		}
	}











    return 0;
}