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

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

/*****
题目来源：2020牛客暑期多校训练营（第一场）H-Minimum-cost Flow

题目链接：https://ac.nowcoder.com/acm/contest/5666/H

题目类型：网络流-最小费用流 

题目大意：n个点，m条边，每条边的花费为c，源点的流量为1， 
  		  q次询问，每次把边的容量变为u/v，求最小费用 

题目思路：由于u/v出现了分数，我们可以把容量*v变成u，那么源点的流量则为v;
首先令容量全为1，求出单位流量下费用流的过程，记录下每次增广花费的费用， 
在q次询问的时候，每次增广u，剩下的流量就是u-v，然后继续增广，直到结束，
结束后，如果仍然有剩余流量，则发生错误，输出"NaN",否则输出费用/v的最简分数  
*****/

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 55;
const ll inf=1e18;

struct Edge{
    int from, to;
	ll cap, flow, cost;
};

vector<ll>mp;

struct MCMF{
    int n, m, s, t;
    vector<Edge> edges;
    vector<int> g[N];
    int inq[N];             //是否在队列中 
    ll d[N];               //最小费用 
    int p[N];               //上一条弧 
    ll a[N];               //可改进量 

    void init(int n,int s,int t){
        this->n = n;this->s=s;this->t=t;
        for(int i = 1; i <= n; i++) g[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, ll cap, ll cost){
        edges.push_back((Edge){from, to, cap, 0, cost});
        edges.push_back((Edge){to, from, 0, 0, -cost});
        m = edges.size();
        g[from].push_back(m-2);
        g[to].push_back(m-1);
    }
	bool BellmanFord(int s, int t, ll& flow, ll& cost){
	    for(int i = 0; i <= n; i++) d[i] = inf;
	    memset(inq, 0, sizeof(inq));
	    d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = inf;
	
	    queue<int> Q;
	    Q.push(s);
	    while(!Q.empty()){
	        int u = Q.front(); Q.pop();
	        inq[u] = 0;
	        for(int i = 0; i < g[u].size(); i++){
	            Edge& e = edges[g[u][i]];
	            if(e.cap > e.flow && d[e.to] > d[u] + e.cost){
	                d[e.to] = d[u] + e.cost;
	                p[e.to] = g[u][i];
	                a[e.to] = min(a[u], e.cap - e.flow);
	                if(!inq[e.to]){Q.push(e.to); inq[e.to] = 1;}
	            }
	        }
	    }
	    if(d[t] == inf) return false;
	    flow += a[t];
	    cost += d[t] * a[t];
	    int u = t;
	    while(u != s){
	        edges[p[u]].flow += a[t];
	        edges[p[u]^1].flow -= a[t];
	        u = edges[p[u]].from;
	    }
	    return true;
	}

	ll Mincost(){
	    ll flow = 0, cost = 0;
	    while(BellmanFord(s, t, flow, cost)){
			mp.push_back(d[t]);  ///记录每次增广花费的费用 
		}
	    return flow;
	}
}mf;


int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m)){
		mp.clear();
		mf.init(n,1,n);
		for(int i=1;i<=m;i++){
			int u,v;
			ll w;
			scanf("%d%d%lld",&u,&v,&w);
			mf.AddEdge(u,v,1,w);
		}
		mf.Mincost();
		int q;
		scanf("%d",&q);
		while(q--){
			int u,v;
			scanf("%d%d",&u,&v);
			ll ansu=0,ansv=v;
			for(int i=0;i<mp.size();i++){
				if(v>u){
					ansu+=mp[i]*u;
					v-=u;
				}
				else{
					ansu+=mp[i]*v;
					v=0;
				}
			} 
			if(v) {
				puts("NaN");continue;
			}
			int x=__gcd(ansu,ansv);
			printf("%lld/%lld\n",ansu/x,ansv/x);
		}
	}
	return 0;
}

 

本文地址：https://blog.csdn.net/LeBron_Yang/article/details/107330532