2020牛客暑期多校训练营（第一场）H

题目描述

  Bobo has a network of nodes and arcs. The -th arc goes from the -th node to the -th node, with cost .
  Bobo also asks questions. The -th question is specified by two integers and , which is to ask the minimum cost to send one unit of flow from the -st node to the -th node, when all the edges have capacity (a fraction).
  You can refer the wiki page for further information of Minimum-cost Flow.

输入描述

  The input consists of several test cases terminated by end-of-file.
  The first line of each test case contains two integers and . The -th of the following lines contains three integers and . The next line contains an integer . The -th of the last lines contains two integers and .
  , , , .
  , , .
  The sum of does not exceed . The sum of does not exceed .

输出描述

  For each test case, print fractions (or NaN, if it is impossible to send one unit of flow) which denote the answer.

示例1

输入

2 1
1 2 2
1
1 1
2 2
1 2 1
1 2 2
3
1 2
2 3
1 4

输出

2/1
3/2
4/3
NaN

分析

  运行 次最小费用流算法显然是不现实的，应当考虑的是：运行一次最小费用流，进行一些预处理，使得每次询问时能够在较短时间内给出答案。
  题中有一重要信息：每条边的容量都相同。设这个容量为 。利用 算法求最小费用最大流，会不断用 算法寻找单位费用和最小的增广路；由于每条边的容量都为 ，故每条边只会存在满流或零流的情况，每次增广获得的最大流改进量恒为 。若源点流量为 且 不超过最大流，就是最小费用流模型。对于这样特殊的（每条边容量都为 ）最小费用流模型，仍然可以利用 算法，每次增广后相当于将流量 减少 ，产生的费用是增广路单位费用和与 的乘积；而最后一次增广时费用的改进量为剩余流量 与增广路单位费用和的乘积。进行多轮增广，直至剩余流量为零，就能得到最小费用流。
  由于每条边的费用 是不变的，因此不论 如何变化，只要源点流量不超过当前网络的最大流，对 次询问中的每一张网络进行 算法，找到的增广路都是相同的，且每条增广路的顺序也保持不变。因此，只需要进行一次最小费用流的计算，记录下每一条增广路的单位费用即可，根据 算法原理，这些增广路是按照单位费用和由小到大获得的，排序操作是多余的。
  不妨令每条边的容量为 ，求一次最小费用最大流，记录下每一条增广路的单位费用。对于每一次询问，源点流量为 ，每条边容量为 。为了减少计算的误差，可以将所有数量扩大 倍，即网络中源点流量为 ，每条边容量为 。若源点流量 不超过网络最大流，那么求固定流量 的最小费用流得过程中，增广路为最小费用最大流得增广路子集，且每一轮 获得的增广路一定是当前所有存在的增广路中费用最小的。每一轮增广，源点流量就减少 ，相应的费用为该增广路的单位费用与 的乘积；最后一次增广，源点流量减少 ，对应费用也要相应改变；最终，源点流量为 ，求得最小费用流 。 即为一次询问的答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第一场） Problem H
Date: 7/24/2020 
Description: Minimum-cost Flow
*******************************************************************/
#include<cstring>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int N=104;
const int M=203;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m;//n个点，m条边
int tot;
int head[N];
struct E
{
    int to;
    int Next;
    ll cap;//容量
    ll cost;//费用
}edge[M<<2];
vector<ll>span;//增广路单位费用
int pre[N];//记录增广路前驱
ll incf[N];//增广路上剩余最小容量
ll dis[N];//将费用看作边权求最短路
bool vis[N];//记录访问
int s,t;//源点 汇点
ll maxflow,mincost;//最小费用最大流
inline void init();//初始化
inline void add_edge(int,int,int,int);
bool SPFA();//找增广路
void update();//更新最长增广路容量
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        while(m--)
        {
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            add_edge(u,v,1,c);
            add_edge(v,u,0,-c);
        }
        while(SPFA())
        {
            update();
            //记录每一条增广路的单位费用
            span.push_back(dis[t]);
        }
        int q;
        scanf("%d",&q);
        while(q--)
        {
            ll u,v;
            scanf("%lld%lld",&u,&v);
            //流量v 容量u
            if(maxflow*u<v) puts("NaN");//流量大于最大流
            else
            {
                ll flow=v,cap=u;
                ll ans=0;
                //按照费用由小到大的顺序访问所有增广路
                for(auto cost:span)
                {
                    if(flow>=u)
                    {
                        flow-=u;
                        ans+=u*cost;
                    }
                    else 
                    {
                        ans+=flow*cost;
                        break;
                    }
                }
                //输出最简分式
                ll g=__gcd(ans,v);
                printf("%lld/%lld\n",ans/g,v/g);
            }
        }
    }
    return 0;
}
inline void init()
{
    s=1;
    t=n;
    memset(head,-1,sizeof(head));
    tot=1;
    span.clear();
    memset(pre,0,sizeof(pre));
    maxflow=mincost=0;
}
inline void add_edge(int u,int v,int cap,int cost)
{
    tot++;
    edge[tot].to=v;
    edge[tot].cap=cap;
    edge[tot].cost=cost;
    edge[tot].Next=head[u];
    head[u]=tot;
}
bool SPFA()
{
    queue<int>q;
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    incf[s]=inf;
    while(!q.empty())
    {
        int x=q.front();
        vis[x]=0;
        q.pop();
        for(register int i=head[x];~i;i=edge[i].Next)
        {
            if(!edge[i].cap) continue;//剩余容量为0，不在残量网络中
            int y=edge[i].to;
            if(dis[y]>dis[x]+edge[i].cost)
            {
                dis[y]=dis[x]+edge[i].cost;//松弛操作
                incf[y]=min(incf[x],edge[i].cap);//最小剩余容量
                pre[y]=i;//记录前驱
                if(!vis[y])
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
    if(dis[t]==inf) return 0;//汇点不可达，已经求出最大流
    else return 1;
}
void update()
{
    int x=t;
    //沿着前驱倒着走增广路
    while(x!=s)
    {
        int y=pre[x];
        edge[y].cap-=incf[t];
        edge[y^1].cap+=incf[t];
        x=edge[y^1].to;
    }
    maxflow+=incf[t];
    mincost+=dis[t]*incf[t];
}