https://ac.nowcoder.com/acm/contest/5666/H

題目大意：給出了每一條邊的費用，有q個詢問，問當每一條邊的容量為u/v時，通過1流量的最小費用是多少。

思路：很明顯這道題只能跑一次費用流，那我們跑一次全部邊容量為1的費用流，當詢問的時候，直接全部擴大v倍，這樣容量就變成u倍，流量變成v。

我們先判斷一下maxflow*u<v的好，最大流小于v了，直接輸出nan；

MCMF每次尋找增廣路徑的時候，都是找一條直通的路徑，因為所有的容量都相等，所以每一次增廣路徑都是滿流的，所以每一次增廣 都是走了u的流量，然后到v=a*v+b，走了a次u后，再走一次b就完成了。

參考：參考的大神題解

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se second #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define ac cout<<ans<<"\n" #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=1e9+7; const ll N =1e6+10; const double eps = 1e-4; //const double pi=acos(-1); ll qk(ll a,ll b){ll ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b/=2;}return ans%mod; } int n,m; namespace MCMF{const int MAXN = 5001;const int MAXM = 50001;int idx =0;ll maxflow, mincost;int n,s,t;ll dis[MAXN], h[MAXN], incf[MAXN], pre[MAXN];//dis表示費用最短路，incf表示當前增廣路上最小流量，pre表示前驅bool vis[MAXN];struct Edge {ll next, to, flow,dis;} e[MAXM << 1];inline void addedge(int from, int to, int flow, int dis){e[idx] = {h[from],to,flow,dis};h[from] = idx++;}inline bool spfa(){queue <int> q;memset(dis, 0x3f, sizeof(dis));memset(vis, 0, sizeof(vis));q.push(s);dis[s] = 0;vis[s] = 1;incf[s] = INF;while(!q.empty()){int u = q.front();vis[u] = 0;q.pop();for(int i = h[u]; ~i; i = e[i].next){if(!e[i].flow) continue;//沒有剩余流量int v = e[i].to;if(dis[v] > dis[u] + e[i].dis){dis[v] = dis[u] + e[i].dis;incf[v] = min(incf[u], e[i].flow);//更新incfpre[v] = i;if(!vis[v])vis[v] = 1, q.push(v);}}}if(dis[t] == INF) return 0;return 1;}vector<ll> res;//每次增廣路的最少費用inline void main(int _n,int _s,int _t){s=_s;n=_n;t=_t;while(spfa()) //如果有增廣路{// cout<<1<<endl;int x = t;maxflow += incf[t];mincost += dis[t] * incf[t];res.push_back(dis[t]);int i;while(x != s) //遍歷這條增廣路，正向邊減流反向邊加流{i = pre[x];e[i].flow -= incf[t];e[i^1].flow += incf[t];x = e[i^1].to;}}}inline void init(){res.clear();memset(pre, 0, sizeof(pre));memset(incf, 0x3f, sizeof(incf));memset(h, -1, sizeof(h));idx = 0;maxflow = mincost = 0;} } void sovle(){while(cin>>n>>m){MCMF::init();for(int i=1;i<=m;i++){int u,v,c;cin>>u>>v>>c;MCMF::addedge(u,v,1,c);MCMF::addedge(v,u,0,-c);}int q;cin>>q;MCMF::main(n,1,n);while(q--){ll u,v;cin>>u>>v;if(MCMF::maxflow*u<v) cout<<"NaN\n";else {ll ans=0;ll tmp=v;for(int k :MCMF::res){if(v>u){v-=u;ans+=u*k;}else {ans+=v*k;break;}}ll g=__gcd(ans,tmp);cout<<ans/g<<"/"<<tmp/g<<"\n";}}} } int main() { #ifdef LOCALfreopen("in.txt", "r", stdin); #elseiosint t=1;//cin>>t;while(t--) sovle(); #endif // LOCALreturn 0; }

總結

以上是生活随笔為你收集整理的2020牛客多校第1场H-Minimum-cost Flow-最小费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。