2020牛客暑期多校训练营（第一场） 网络流 Minimum-cost Flow
题目大意：
给你网络流的一个图，然后又q次询问，每次问如果所有的边的容量都是 (frac{u}{v}) 那么请给出流1的最小费用，如果无法流1，那么输出 (NaN)
题解：
这场题目都比较难，所以其实有点被吓到的，但是这个题目看了看题解，发现其实不是很难。。
-
定义 (cost(c,f)) 表示所有的弧的容量都是 (c) ，最后的流量是 (f) 的最小花费。
-
明确这个题目只能跑一次网络流，是不可能跑q次网络流的，所以要首先跑一次网络流，之后再借助这次的结果进行运算
-
首先跑一次所有弧的容量都是1的网络流，最后算出来的结果就是 (cost(1,f))
-
目标是 (cost(frac{u}{v},1)) 接下来就对式子进行转化
- (cost(frac{u}{v},1)) = (cost(1,frac{v}{u})*frac{v}{u})
- 假设对于第 (i) 次找增广路的流量是 (f[i]) 花费是 (c[i])
- 每单位流量的花费就是 (frac{c[i]}{f[i]})
- 所以正常来算就是 ((sum(frac{c[i]}{f[i]}*frac{v}{u}))*frac{u}{v})
- 最后这个算要分情况讨论，如果此时的流量要小于 (frac{v}{u}) 也就是 (f[i]*u<v) 那么就是 (frac{c[i]}{f[i]}*f[i]*frac{u}{v})
- 如果此时的流量要是大于 (frac{u}{v}) 那么答案就是前面的答案加上 (frac{c[i]}{f[i]}*frac{v}{u}*frac{u}{v})
-
最后一个需要知道的点是，为什么在后面求答案找花费的时候就一定是按照 (spfa) 找最短路的顺序来求。
这个是因为每一条增广路的流量一定是1，所以 (f[i]=1) 所以我只要 (c[i]) 从小到大排序，按照这样的顺序来找答案，那么每次的计算完的花费一定是到目前位置最少的，也就是说一定是最优解。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1000 + 10;
struct edge
{
int u, v, c, f, cost;
edge(int u, int v, int c, int f, int cost):u(u), v(v), c(c), f(f), cost(cost){}
};
vector<edge>e;
vector<int>G[maxn];
int a[maxn];//找增广路每个点的水流量
int p[maxn];//每次找增广路反向记录路径
int d[maxn];//SPFA算法的最短路
int inq[maxn];//SPFA算法是否在队列中
int n, m,cur;
ll cc[maxn],ff[maxn];
void init(int n)
{
cur=0;
for(int i = 0; i <= n; i++)G[i].clear();
e.clear();
}
void addedge(int u, int v, int c, int cost)
{
e.push_back(edge(u, v, c, 0, cost));
e.push_back(edge(v, u, 0, 0, -cost));
int m = e.size();
G[u].push_back(m - 2);
G[v].push_back(m - 1);
}
bool bellman(int s, int t, int& flow, long long & cost)
{
for(int i = 0; i <= n + 1; i++)d[i] = INF;//Bellman算法的初始化
memset(inq, 0, sizeof(inq));
d[s] = 0;inq[s] = 1;//源点s的距离设为0，标记入队
p[s] = 0;a[s] = INF;//源点流量为INF（和之前的最大流算法是一样的）
queue<int>q;//Bellman算法和增广路算法同步进行，沿着最短路拓展增广路，得出的解一定是最小费用最大流
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 & now = e[G[u][i]];
int v = now.v;
if(now.c > now.f && d[v] > d[u] + now.cost)
//now.c > now.f表示这条路还未流满（和最大流一样）
//d[v] > d[u] + e.cost Bellman 算法中边的松弛
{
d[v] = d[u] + now.cost;//Bellman 算法边的松弛
p[v] = G[u][i];//反向记录边的编号
a[v] = min(a[u], now.c - now.f);//到达v点的水量取决于边剩余的容量和u点的水量
if(!inq[v]){q.push(v);inq[v] = 1;}//Bellman 算法入队
}
}
}
if(d[t] == INF)return false;//找不到增广路
flow += a[t];//最大流的值，此函数引用flow这个值，最后可以直接求出flow
cost += (long long)d[t] * (long long)a[t];//距离乘上到达汇点的流量就是费用
cc[++cur] = (long long)d[t] * (long long)a[t];
ff[cur] = a[t];
for(int u = t; u != s; u = e[p[u]].u)//逆向存边
{
e[p[u]].f += a[t];//正向边加上流量
e[p[u] ^ 1].f -= a[t];//反向边减去流量 （和增广路算法一样）
}
return true;
}
int MincostMaxflow(int s, int t, long long & cost)
{
cost = 0;
int flow = 0;
while(bellman(s, t, flow, cost));//由于Bellman函数用的是引用，所以只要一直调用就可以求出flow和cost
return flow;//返回最大流，cost引用可以直接返回最小费用
}
ll gcd(ll x,ll y){
return y==0?x:gcd(y,x%y);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
init(n);
for(int i=1;i<=m;i++){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
addedge(u,v,1,c);
}
ll cost = 0;
int flow = MincostMaxflow(1,n,cost);
int q;
scanf("%d",&q);
while(q--){
int u,v;
scanf("%d%d",&u,&v);
ll x=0,y=v;
if(flow*1ll*u<v) {
printf("NaN
");
continue;
}
for(int i=1;i<=cur;i++){
// printf("cc[%d]=%lld ff[%d]=%lld
",i,cc[i],i,ff[i]);
if(v>u*ff[i]) x+=cc[i]*u,v-=ff[i]*u;
else{
x+=cc[i]*v/ff[i];
v=0;
}
// printf("x=%lld y=%lld v=%d
",x,y,v);
if(!v) break;
}
if(v) printf("NaN
");
else {
ll g = gcd(x,y);
x/=g,y/=g;
printf("%lld/%lld
",x,y);
}
}
}
return 0;
}