2020牛客暑期多校训练营（第一场）Minimum-cost Flow 费用流

题目链接：https://ac.nowcoder.com/acm/contest/5666
题目大意：给你一个n,m和m条有向边ai->bi和费用ci。
每次询问u/v。回答把每条边的费用修改为u/v时。从1流一个流量到n的最小费用。如果无法流到输出NaN。其实就是把所以边容量修改为u。从1流v的流量到n的费用/v。

思路：对于每次询问我们不能跑一次费用流。因为容量一样。你们我们根据费用流的算法流程。在每次寻找增广路SPAF()时。都会找到流量为1的路。我们统计下每个流量下的费用sum[i]和第i条增广路的费用s1[i]。那么我们在出来询问时。判断最大流*u<v就NaN，否则就选择前u/v条增广路，每条流量为v。和第u/v+1条增广路流量为u%v。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL maxn=305;

LL s1[305], sum[305], tot=0;
struct Mcmf_flow{
    bool vis[maxn];
    LL dis[maxn];
    LL pre[maxn];
    LL last[maxn];
    LL flow[maxn];
    LL zdl, fy;
    //dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量
    struct Edge {
        LL to,next,flow,dis;//flow流量 dis花费
    } e[maxn];
    LL head[maxn],cut;
    queue <LL> q;

    void init(){
        memset(s1, 0, sizeof(s1));
        memset(sum, 0, sizeof(sum));
        memset(head,-1,sizeof(head));
        tot=0;
        cut=-1;//初始化
        zdl=fy=0;
    }

    void add_e(LL from,LL to,LL flow,LL dis) {
        e[++cut].next=head[from];
        e[cut].to=to;
        e[cut].flow=flow;
        e[cut].dis=dis;
        head[from]=cut;
    }

    void add(LL x, LL y, LL z, LL f){
        add_e(x,y,z,f);
        add_e(y,x,0,-f);
    }

    bool spfa(LL s,LL t) {
        memset(dis,0x7f,sizeof(dis));
        memset(flow,0x7f,sizeof(flow));
        memset(vis,0,sizeof(vis));
        q.push(s);
        vis[s]=1; dis[s]=0; pre[t]=-1;
        while (!q.empty()) {
            LL now=q.front();
            q.pop(); vis[now]=0;
            for (LL i=head[now]; i!=-1; i=e[i].next) {
                if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].dis) { //正边
                    dis[e[i].to]=dis[now]+e[i].dis;
                    pre[e[i].to]=now;
                    last[e[i].to]=i;
                    flow[e[i].to]=min(flow[now],e[i].flow);//
                    if (!vis[e[i].to]) {
                        vis[e[i].to]=1;
                        q.push(e[i].to);
                    }
                }
            }
        }
        return pre[t]!=-1;
    }

    void MCMF(LL s, LL t) {
        while (spfa(s,t)) {
            LL now=t;
            zdl+=flow[t];
            fy+=flow[t]*dis[t];
            sum[++tot]=fy;//得到sum[]
            s1[tot]=sum[tot]-sum[tot-1];//得到s1[]

            while (now!=s) {
                //从源点一直回溯到汇点
                e[last[now]].flow-=flow[t];//flow和dis容易搞混
                e[last[now]^1].flow+=flow[t];
                now=pre[now];
            }
        }
    }

}min_Flow;

int main() {
    LL n,m,s,t,x,y,z,f;
    while(~scanf("%lld%lld", &n, &m)){
        min_Flow.init();
        for (LL i=1; i<=m; i++) {
            scanf("%lld%lld%lld",&x,&y,&f);
            min_Flow.add(x,y,1,f);
        }
        s=1, t=n;
        min_Flow.MCMF(s, t);
        LL mx=min_Flow.zdl;
        LL q; scanf("%lld", &q);
        while(q--){

            LL u, v; scanf("%lld%lld", &u, &v);
            LL w=v/u;
            if(mx*u<v){
                printf("NaN\n");
            }
            else{
                LL ans=sum[v/u]*u+s1[w+1]*(v%u);
                LL gcd=__gcd(v, ans);
                printf("%lld/%lld\n", ans/gcd, v/gcd);
            }
        }
    }

    return 0;
}