欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-10 15:46:27
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,那么源点的流...

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