本文共 2966 字，大约阅读时间需要 9 分钟。

这题没有考察建图,而是考察费用流的本质。

比如每次spfa只会找一条增广路

比如越先找到的增广路花费一定越小

$首先发现容量为u/v是没办法算的(分数)$

$边容量u/v,最大流是1$

$转化为边容量u,最大流是v(这样花费最后要除以v)$

$面对这么多询问,我们预处理一下每条增广路的花费就行了$

$按题目建图,流量暂时设置为1,因为好算$

$每次spfa后,到t的流量一定是1,所以只需要记录每条增广路的花费在path数组$

$那么现在每个询问里边容量是u,最大流是v$

$设v=au+b(b<u)$

$因为每条边的容量是u,所以至少需要a条增广路$

$如果b不为0,那么第a+1条增广路需要走\frac{b}{u}$

$所以设sumn是path的前缀和数组$

$花费是sumn[x]+path[x+1]\ast b/u$

但是不要忘记sumn是容量为1的花费

现在容量是u,那么还需要乘以u

$所以花费是sumn[x]\ast u+path[x+1]\ast b$

$再除以v就好啦!因为1到n只需要1的流量而不是v的流量$

#include 
   
    using namespace std;#define int long longconst int maxn=2e5+10;const int inf=1e9;int n,m,s,t;struct edge{	int to,nxt,flow,w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int flow,int w){	d[++cnt]=(edge){v,head[u],flow,w},head[u]=cnt;	d[++cnt]=(edge){u,head[v],0,-w},head[v]=cnt;}int dis[maxn],vis[maxn],top,path[maxn],sumn[maxn],flow[maxn],pre[maxn];bool spfa(){	for(int i=0;i<=t;i++)	dis[i]=inf,vis[i]=0;	dis[s]=0; flow[s]=inf;	queue
    
     q; q.push( s );	while( !q.empty() )	{		int u=q.front(); q.pop();		vis[u]=0;		for(int i=head[u];i;i=d[i].nxt )		{			int v=d[i].to;			if( d[i].flow&&dis[v]>dis[u]+d[i].w )			{				dis[v]=dis[u]+d[i].w;				flow[v]=min( flow[u],d[i].flow );				pre[v]=i;				if( !vis[v] )	vis[v]=1,q.push( v );			}		}	}	return dis[t]!=inf;}void dinic(){	while( spfa() )	{		int x=t;		path[++top]=dis[t];	//第top条增广路的花费,流量一定是1,所以没乘flow[t] 		while( x!=s )		{			int i=pre[x];			d[i].flow-=1;			d[i^1].flow+=1;			x=d[i^1].to;		}	}}int gcd(int a,int b){	return b==0?a:gcd(b,a%b);}signed main(){	while( cin >> n >> m )	{		for(int i=1;i<=m;i++ )		{			int l,r,w;			scanf("%lld%lld%lld",&l,&r,&w);			add(l,r,1,w);		}		s=1,t=n;		dinic();		for(int i=1;i<=top;i++)	sumn[i]=sumn[i-1]+path[i];		int q; cin >> q;		while( q-- )		{			int u,v;			scanf("%lld%lld",&u,&v);			if( u==0 )			{				cout << "NaN\n";				continue;			}			int x=v/u,y=v%u;			if( x>top || ((x+1)>top&&y) )	cout << "NaN\n";			else			{				int cost=sumn[x]*u+path[x+1]*y;				int yin=gcd(cost,v);				printf("%lld/%lld\n",cost/yin,v/yin);			}		}		for(int i=1;i<=n;i++)	head[i]=0;		cnt=1,top=0;	}}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108181087 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！