题面:
题意:
给出一张有向图, ai−>bi 的花费为 ci (就是很迷,我就是读不出出题人想说单位流量的感觉,但是看样例,这个 ci 就是单位流量),现在给出 q 次询问,每次询问给出一个 u 和 v 需要回答:将所有边的流量都设置为 vu 后,从点 1 到点 n 流量为 1 时的最小花费为多少。
题解:
先理解一下费用流算法:
费用流是先用spfa求解一条源点到汇点单位花费最小的路,然后取这条路上的最小流量。
直到源点不能达到汇点。
我们先将每条边的流量设为 1,每次增广只会使流量增加 1(因为是找了一条路径,取了路径上的最小流量)。
我们记录下流量为1,2,3 等等的花费。
现在询问将所有边的流量都设为 vu 后,从点 1 到点 n 流量为 1 时的最小花费。
初始时求解了每条边设为 1 时的最小花费,现在要将每条边设为 vu ,求总流量为 1 时的最小花费,那么就相当于初始时每条边设为 1 ,求总流量为 uv 的最小花费 ans。
然后我们 1−>u/v,ans−>ans∗(u/v)
我们设sum为这些花费的前缀和,设 k=v/u 为整除。
最终的 ans=u/v∗(sum[k]+(v/u−k)∗(sum[k+1]−sum[k]))
ans=(sum[k]∗u+((v−k∗u)∗(sum[k+1]−sum[k]))/v
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=55;
const int maxm=210;
const int up=1000;
int head[maxn],ver[maxm],edge[maxm],cost[maxm],nt[maxm];
int d[maxn],incf[maxn],pre[maxn],v[maxn];
ll sum[maxm];
int tot,s,t,cnt;
void init(void)
{
memset(head,0,sizeof(head));
tot=1;
cnt=0;
}
void add(int x,int y,int z,int c)
{
ver[++tot]=y,edge[tot]=z,cost[tot]=c;
nt[tot]=head[x],head[x]=tot;
ver[++tot]=x,edge[tot]=0,cost[tot]=-c;
nt[tot]=head[y],head[y]=tot;
}
bool spfa(void)
{
queue<int>q;
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
q.push(s);
d[s]=0;
v[s]=1;
incf[s]=inf;
while(q.size())
{
int x=q.front();
v[x]=0;
q.pop();
for(int i=head[x];i;i=nt[i])
{
if(!edge[i]) continue;
int y=ver[i];
if(d[y]>d[x]+cost[i])
{
d[y]=d[x]+cost[i];
incf[y]=min(incf[x],edge[i]);
pre[y]=i;
if(!v[y]) v[y]=1,q.push(y);
}
}
}
if(d[t]==inf) return false;
return true;
}
void update(void)
{
int x=t;
while(x!=s)
{
int i=pre[x];
edge[i] -= incf[t];
edge[i^1] += incf[t];
x=ver[i^1];
}
sum[++cnt]=d[t];
}
void getmaxx(void)
{
while(spfa()) update();
}
ll gcd(ll a,ll b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int main(void)
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
s=1,t=n;
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,1,z);
}
getmaxx();
for(int i=1;i<=cnt;i++)
sum[i]+=sum[i-1];
int q;
ll u,v;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%lld%lld",&u,&v);
if(u*cnt<v)
{
printf("NaN\n");
continue;
}
ll k=v/u;
ll ans1=sum[k]*u+(v-k*u)*(sum[k+1]-sum[k]);
ll ans2=v;
ll gc=gcd(ans1,ans2);
printf("%lld/%lld\n",ans1/gc,ans2/gc);
}
}
return 0;
}