题解 CF1307G Cow and Exercise

· · 题解

阅读本文需要您对于线性规划的对偶原理有一定的了解，建议优先阅读 2016 年集训队论文集中 dkf 的《浅谈线性规划与对偶问题》一文。

直接从图论的角度来考虑这个问题是非常困难的，因此我们不妨从线性规划的角度入手。令 d_i 为点 i 对应的最短路的长度，不难得到以下的线性规划：

\begin{aligned} {\rm maximize}: & & & d_n-d_1\\ {\rm constraints}: & & d_v & \le d_u+w_{uv}+a_{uv} & & (u,v)\in E\\ & & \sum_{(u,v)\in E}a_{uv} & \le x\\ & & d_i,a_{uv} & \ge 0 & & i\in V,(u,v)\in E \end{aligned}

你可能注意到我对于 d_i 的定义非常谨慎，因为这并不是一般意义上的最短路的长度，我们并没有指定源点。但显然，d_i 仍然满足三角形不等式的约束。而目标函数 d_n-d_1 则起到了钦定源点为 1 的作用，其所代表的必然是从 1 到 n 的最短路，这一点是容易看出的。

这个线性规划本身依然无法给我们提供很好的思路，因此不妨写出其对偶形式。令约束从上到下分别对应变量 \alpha_{uv} 与 \beta ，那么对偶线性规划即为：

\begin{aligned} {\rm minimize}: & & \beta x+ \sum_{(u,v)\in E}\alpha_{uv}w_{uv}\\ {\rm constraints}: & & \sum_{u\in V}\alpha_{ui}-\sum_{v\in V}\alpha_{iv}&\ge 0 & & i\in V\\ & & \sum_{u\in V}\alpha_{u1}-\sum_{v\in V}\alpha_{1v}&\ge -1\\ & & \sum_{u\in V}\alpha_{un}-\sum_{v\in V}\alpha_{nv}&\ge 1\\ & & \beta-\alpha_{uv} &\ge 0 & & (u,v)\in E \end{aligned}

到这里我们已经可以看出费用流模型的影子了。我们不希望看到 \ge 号，注意到在最优解中每个 d_i 都可以 \neq 0 ，那么根据互补松弛性（即论文中的互松弛定理），我们知道在取最优解的情况下：

\begin{aligned} {\rm minimize}: & & \beta x+ \sum_{(u,v)\in E}\alpha_{uv}w_{uv}\\ {\rm constraints}: & & \sum_{u\in V}\alpha_{ui}-\sum_{v\in V}\alpha_{iv}&= 0 & & i\in V\\ & & \sum_{u\in V}\alpha_{u1}-\sum_{v\in V}\alpha_{1v}&= -1\\ & & \sum_{u\in V}\alpha_{un}-\sum_{v\in V}\alpha_{nv}&= 1\\ & & \beta&\ge \alpha_{uv} & & (u,v)\in E \end{aligned}

若把 \alpha_{uv} 看作流量，那么其具有上界 \beta 。为了使其上界恒定，我们可以从 \alpha _{uv} 中提出一个 \beta ，并令 {\rm flow}=\frac 1\beta ，即：

\begin{aligned} {\rm minimize}: & & \frac {x+ \sum_{(u,v)\in E}\alpha_{uv}w_{uv}}{\rm flow}\\ {\rm constraints}: & & \sum_{u\in V}\alpha_{ui}-\sum_{v\in V}\alpha_{iv}&= 0 & & i\in V\\ & & \sum_{u\in V}\alpha_{u1}-\sum_{v\in V}\alpha_{1v}&= -{\rm flow}\\ & & \sum_{u\in V}\alpha_{un}-\sum_{v\in V}\alpha_{nv}&= {\rm flow}\\ & & \alpha_{uv}&\in [0,1] & & (u,v)\in E \end{aligned}

实际上，我们可以证明，总是存在一组最优解，使得以上各变量的取值均在整数域上。考虑最小费用流的过程，可以发现，当 \rm flow\in[k,k+1]\mid k\in {\mathbb Z} 时，\sum_{(u,v)\in E}\alpha_{uv}w_{uv} ，也就是费用，会体现为一个以 \rm flow 为自变量的一次函数，那么目标函数的最值总是会出现在边界，也就是整数处，此时 \alpha_{uv} 的取值也均为整数。

于是我们如愿以偿的得到了标准的整数域上的最小费用可行流模型，全程的推导严谨自然。剩下的部分就非常简单了，这里仅给出对算法流程的描述：按上述模型中的规则建图，并对所有可行的 \rm flow 预处理出相应的费用 \rm cost 。对于每一次询问，遍历所有 \rm flow 来计算答案。易见 \rm flow < n ，那么总时间复杂度 O(n^2m+nq) 。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl putchar('\n')
const int N=55,inf=0x3f3f3f3f;
typedef double db;
using namespace std;

int n,m,Q,cnt,head[N],S,T,pre[N],dis[N],inq[N],mn[N],c[N],flow;
queue<int> q;
struct edge { int a,b,next,f,v; } e[N*N*2];
void add_edge(int a,int b,int f,int v) {
    e[++cnt]={a,b,head[a],f,v};
    head[a]=cnt;
}
void add(int a,int b,int f,int v) { add_edge(a,b,f,v),add_edge(b,a,0,-v); }

bool spfa() {
    rep(i,1,T) pre[i]=inq[i]=0,dis[i]=inf;
    q.push(S),dis[S]=0,inq[S]=1,mn[S]=inf;
    while(!q.empty()) {
        int x=q.front(); q.pop(),inq[x]=0;
        for(int i=head[x];i;i=e[i].next) {
            if(e[i].f&&dis[e[i].b]>dis[x]+e[i].v) {
                dis[e[i].b]=dis[x]+e[i].v;
                mn[e[i].b]=min(mn[x],e[i].f);
                pre[e[i].b]=i;
                if(!inq[e[i].b]) q.push(e[i].b),inq[e[i].b]=1;
            }
        }
    }
    return pre[T];
}
void edmonds() {
    while(spfa()) {
        rep(i,1,mn[T]) c[flow+i]=c[flow+i-1]+dis[T];
        int x=T; flow+=mn[T];
        while(pre[x]) {
            e[pre[x]].f-=mn[T],e[pre[x]^1].f+=mn[T];
            x=e[pre[x]].a;
        }
    }
}
void init() { S=1,T=n,edmonds(); }

db query(int x) {
    db res=inf;
    rep(i,1,flow) res=min(res,1.0*(x+c[i])/i);
    return res;
}

int main() {
    scanf("%d%d",&n,&m),cnt=1;
    rep(i,1,m) {
        int a,b,v; scanf("%d%d%d",&a,&b,&v);
        add(a,b,1,v);
    }
    init();
    scanf("%d",&Q);
    while(Q--) {
        int x; scanf("%d",&x);
        printf("%.8lf\n",query(x));
    }
    return 0;
}