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

题目描述

Bobo has a network of $n$ nodes and $m$ arcs. The $i$ -th arc goes from the $a_i$ -th node to the $b_i$ -th node, with cost $c_i$ .
Bobo also asks $q$ questions. The $i$ -th question is specified by two integers $u_i$ and $v_i$ , which is to ask the minimum cost to send one unit of flow from the $1$ -st node to the $n$ -th node, when all the edges have capacity $\frac{u_i}{v_i}$ (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 $n$ and $m$ . The $i$ -th of the following $m$ lines contains three integers $a_i, b_i$ and $c_i$ . The next line contains an integer $q$ . The $i$ -th of the last $q$ lines contains two integers $u_i$ and $v_i$ .
$2 \leqslant n \leqslant 50$ , $1 \leqslant m \leqslant 100$ , $1 \leqslant a_i, b_i \leqslant n$ , $1 \leqslant c_i \leqslant 10^5$ .
$1 \leqslant q \leqslant 10^5$ , $0 \leqslant u_i \leqslant v_i \leqslant 10^9$ , $v_i > 0$ .
The sum of $m$ does not exceed $10^4$ . The sum of $q$ does not exceed $10^6$ .

输出描述

For each test case, print $q$ 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

分析

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

代码

/******************************************************************
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];
}