好看云在线网站模板,江西省建设厅教育网站,网络工程师报名入口,国内购物平台排行榜https://ac.nowcoder.com/acm/contest/5666/H
题目大意#xff1a;给出了每一条边的费用#xff0c;有q个询问#xff0c;问当每一条边的容量为u/v时#xff0c;通过1流量的最小费用是多少。
思路#xff1a;很明显这道题只能跑一次费用流#xff0c;那我们跑一次全部边…https://ac.nowcoder.com/acm/contest/5666/H
题目大意给出了每一条边的费用有q个询问问当每一条边的容量为u/v时通过1流量的最小费用是多少。
思路很明显这道题只能跑一次费用流那我们跑一次全部边容量为1的费用流当询问的时候直接全部扩大v倍这样容量就变成u倍流量变成v。
我们先判断一下maxflow*uv的好最大流小于v了直接输出nan
MCMF每次寻找增广路径的时候都是找一条直通的路径因为所有的容量都相等所以每一次增广路径都是满流的所以每一次增广 都是走了u的流量然后到va*vb走了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 rt1
#define rson rt1|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 i0;(i)(n);i)
#define rep1(i,n) for(int i1;(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 coutans\n
#define F(x) ((x)/3((x)%31?0:tb))
#define G(x) ((x)tb?(x)*31:((x)-tb)*32)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll,ll pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod1e97;
const ll N 1e610;
const double eps 1e-4;
//const double piacos(-1);
ll qk(ll a,ll b){ll ans1;while(b){if(b1) 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;}vectorll res;//每次增广路的最少费用inline void main(int _n,int _s,int _t){s_s;n_n;t_t;while(spfa()) //如果有增广路{// cout1endl;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(cinnm){MCMF::init();for(int i1;im;i){int u,v,c;cinuvc;MCMF::addedge(u,v,1,c);MCMF::addedge(v,u,0,-c);}int q;cinq;MCMF::main(n,1,n);while(q--){ll u,v;cinuv;if(MCMF::maxflow*uv) coutNaN\n;else {ll ans0;ll tmpv;for(int k :MCMF::res){if(vu){v-u;ansu*k;}else {ansv*k;break;}}ll g__gcd(ans,tmp);coutans/g/tmp/g\n;}}}
}
int main()
{
#ifdef LOCALfreopen(in.txt, r, stdin);
#elseiosint t1;//cint;while(t--) sovle();
#endif // LOCALreturn 0;
}
