QOJ171 Longest Shortest Path

将最短路写成线性规划形式。

$$\begin{align} \max \quad & p_t-p_s \\ \texttt{s.t.} \quad & p_v-p_u \le d_e+x_e \\ & \sum_{e} c_ex_e \le P \\ & x_e,p_u \ge 0 \end{align}$$

线性规划对偶，记 $out_u,in_u$ 分别为 $u$ 的出、入边集合。那么等价于

$$\begin{align} \min \quad & \sum_{e} d_ef_e + PF \\ \texttt{s.t.} \quad & \sum_{e \in in_s} f_e - \sum_{e \in out_s} f_e \ge -1 \\ & \sum_{e \in in_t} f_e - \sum_{e \in out_t} f_e \ge 1 \\ & \sum_{e \in in_u} f_e - \sum_{e \in out_u} f_e \ge 0 \quad u \in V \setminus \{s,t\} \\ & c_eF - f_e \ge 0 \\ & F,f_e \ge 0 \end{align}$$

由于要取 $\min$ ，所以前三个约束取等号更优，发现是网络流的限制，即

$$\begin{align} \min \quad & \sum_{e} d_ef_e + PF \\ \texttt{s.t.} \quad & f 为 s 到 t 流量为 1 的流 \\ & c_eF - f_e \ge 0 \\ & F,f_e \ge 0 \end{align}$$

要将 $c_eF - f_e \ge 0$ 转化为流量的限制，令 $f’_e = \frac{f_e}{F}$，则

$$\begin{align} \min \quad & (\sum_{e} d_ef'_e + P)F \\ \texttt{s.t.} \quad & f' 为 s 到 t 流量为 \frac{1}{F} 的流 \\ & f'_e \le c_e \\ & F > 0,f'_e \ge 0 \end{align}$$

这是费用流的形式，$\sum_e d_ef’_e + P$ 关于 $\frac{1}{F}$ 是凸的，那么 $(\sum_{e} d_ef’_e + P)F$ 的最小值在凸包的端点处取到，用 EK 求解费用流，每次增广后更新答案即可。记 $F$ 为 $c$ 的上界，时间复杂度 $O(Fnm^2)$，实际上远远跑不满。

还可以用拉格朗日对偶，详见。

#include<bits/stdc++.h>
using namespace std;

using db=double;
const int N=200+10,M=2e3+10,INF=1e9;
inline int chkmin(int &x,int y){ return y<x?x=y,1:0; }
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,s,t,P,maxflow=0,mincost=0; db ans=INF;

int head[N],ne[M*2],v[M*2],fl[M*2],w[M*2],tot=1;
void add(int x,int y,int f,int z){
	ne[++tot]=head[x],head[x]=tot,v[tot]=y,fl[tot]=f,w[tot]=z;
	ne[++tot]=head[y],head[y]=tot,v[tot]=x,fl[tot]=0,w[tot]=-z;
}

int dis[N],vis[N],pre[N],idx[N]; queue<int> q;
int spfa(){
	for(int i=1;i<=n;++i) dis[i]=INF,vis[i]=0; q.push(s),dis[s]=0,vis[s]=1;
	while(!q.empty()){
		int u=q.front(); q.pop(),vis[u]=0;
		for(int i=head[u];i;i=ne[i])
			if(fl[i]&&chkmin(dis[v[i]],dis[u]+w[i]))
				pre[v[i]]=u,idx[v[i]]=i,q.push(v[i]),vis[v[i]]=1;
	}
	return dis[t]!=INF;
}

int main(){

	n=rd,m=rd,P=rd,s=rd,t=rd;
	for(int i=1,x,y,z,f;i<=m;++i) x=rd,y=rd,z=rd,f=rd,add(x,y,f,z);
	
	while(spfa()){
		int dflow=INF; for(int i=t;i!=s;i=pre[i]) dflow=min(dflow,fl[idx[i]]);
		maxflow+=dflow,mincost+=dis[t]*dflow;
		for(int i=t;i!=s;i=pre[i]) fl[idx[i]]-=dflow,fl[idx[i]^1]+=dflow;
		ans=min(ans,(db)(P+mincost)/maxflow);
	}
	
	printf("%.6lf\n", ans);

	return 0;
}