题目描述：
文章图片
题目分析：
文章图片
求最大费用可行流即可。路径的长度指路径上的 t i t_i ti?之和。
对偶理论：
变量非负，约束不等式同号，下面这张图截自百度百科对偶理论
文章图片
LOJ上有不二分的做法，8是太懂。。虽然上面这个做法也很玄学 （Upd，后文补充了）
Upd：更好的理解体验请阅读 2016国家集训队论文《浅谈线性规划与对偶问题》
【LOJ#6511. 「雅礼集训 2018 Day8」B【线性规划对偶问题，费用流】】Code：
#include
#define maxn 125
#define maxm 1505
using namespace std;
const int inf = 0x3f3f3f3f;
int n,m,W,S,T;
int fir[maxn],nxt[maxm],to[maxm],c[maxm],w[maxm],tot=1;
void line(int x,int y,int z,int v){
nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y,c[tot]=z,w[tot]=v;
nxt[++tot]=fir[y],fir[y]=tot,to[tot]=x,c[tot]=0,w[tot]=-v;
}
int X[405],Y[405],sum,t[maxn],C[maxn];
int dis[maxn],pp[maxn],pe[maxn];
queueq;
bool inq[maxn];
bool SPFA(){
memset(dis,0x3f,(T+1)<<2);
q.push(T),dis[T]=0;
while(!q.empty()){
int u=q.front();
q.pop(),inq[u]=0;
for(int i=fir[u],v;
i;
i=nxt[i]) if(c[i^1]&&dis[v=to[i]]>dis[u]+w[i^1]){
dis[v]=dis[u]+w[i^1],pp[v]=u,pe[v]=i^1;
if(!inq[v]) inq[v]=1,q.push(v);
}
}
return dis[S]<0;
}
bool check(int mid){
memset(fir,0,(T+1)<<2),tot=1;
for(int i=1;
i<=n;
i++)
line(S,i,inf,mid),
line(i,i+n,C[i],-t[i]),
line(i,i+n,inf,0),
line(i+n,T,inf,0);
for(int i=1;
i<=m;
i++) line(X[i]+n,Y[i],inf,0);
int ans=0;
while(SPFA()){
int mn=inf;
for(int x=S;
x!=T;
x=pp[x]) mn=min(mn,c[pe[x]]);
ans+=mn*dis[S];
for(int x=S;
x!=T;
x=pp[x]) c[pe[x]]-=mn,c[pe[x]^1]+=mn;
}
return -ans<=W;
}
int main()
{
scanf("%d%d%d",&n,&m,&W);
for(int i=1;
i<=n;
i++) scanf("%d",&t[i]),sum+=t[i];
for(int i=1;
i<=n;
i++) scanf("%d",&C[i]);
for(int i=1;
i<=m;
i++) scanf("%d%d",&X[i],&Y[i]);
S=0,T=2*n+1;
int l=0,r=sum,mid;
while(l>1)?(r=mid):(l=mid+1);
printf("%d\n",l);
}
Upd：LP对偶费用流解法
听完dls的LP对偶费用流归来啦！（虽然还有点迷糊）
线性规划
minimize ∑ c ( u , v ) max ? ( h u ? h v + w ( u , v ) , 0 ) \text{minimize} \sum c(u,v)\max(h_u-h_v+w(u,v),0) minimize∑c(u,v)max(hu??hv?+w(u,v),0)
可以转化为最大费用循环流， u u u 向v v v 连流量为c ( u , v ) c(u,v) c(u,v)，费用为w ( u , v ) w(u,v) w(u,v) 的边，其中h h h 为自己定义的 ≥ 0 \ge 0 ≥0 的变量。
具体证明可以根据最大费用循环流的线性规划模型对偶回去，网上也有。
我们把u u u 点安装完成的时间设为T u T_u Tu?，减少时间设为δ u \delta_u δu?，那么限制条件就是T v ≥ T u + t v ? δ v T_v\ge T_u+t_v-\delta_v Tv?≥Tu?+tv??δv?。
二分答案之后我们想要最小化∑ δ v ? c v \sum \delta_v*c_v ∑δv??cv?，但是δ v \delta_v δv? 的限制条件有多个，无法取等，把点拆成两个： x u x_u xu? 和y u y_u yu?，分别表示前面所有安装包安装完成的时间，和u u u 安装完成的时间。
最开始的问题可以表述为：
minimizey e n d s.t.y v ? x v ? t v + δ v ≥ 0 y u ≤ x v δ v ≤ t v ∑ δ v ? c v ≤ w \text{minimize} ~y_{end}\\ \text{s.t.}~~~~~y_v-x_v-t_v+\delta_v\ge 0\\ y_u\le x_v\\ \delta_v\le t_v\\ \sum \delta_v*c_v\le w minimize yend?s.t.yv??xv??tv?+δv?≥0yu?≤xv?δv?≤tv?∑δv??cv?≤w
二分答案λ \lambda λ，问题转化为：
minimize ∑ δ v ? c v s.t.y v ? x v ? t v + δ v ≥ 0 y u ≤ x v δ v ≤ t v y v ≤ λ \text{minimize} \sum\delta_v*c_v\\ \text{s.t.}~~~~~y_v-x_v-t_v+\delta_v\ge 0\\ y_u\le x_v\\ \delta_v\le t_v\\ y_v\le \lambda minimize∑δv??cv?s.t.yv??xv??tv?+δv?≥0yu?≤xv?δv?≤tv?yv?≤λ
最优情况下δ v = max ? ( x v ? y v + t v , 0 ) \delta_v=\max(x_v-y_v+t_v,0) δv?=max(xv??yv?+tv?,0)
因为是最小化，所以y u ≤ x v y_u\le x_v yu?≤xv? 可以用∞ ? max ? ( y u ? x v , 0 ) \infty*\max(y_u-x_v,0) ∞?max(yu??xv?,0) 的代价来表示。
δ v ≤ t v \delta_v\le t_v δv?≤tv? 即x v ≤ y v x_v\le y_v xv?≤yv?，代价为∞ ? max ? ( x v ? y v , 0 ) \infty*\max(x_v-y_v,0) ∞?max(xv??yv?,0)
为了方便，我们新建两个点S , T S,T S,T， S ≤ x v S\le x_v S≤xv?， y v ≤ T y_v\le T yv?≤T，分别为∞ ? max ? ( S ? x v , 0 ) \infty*\max(S-x_v,0) ∞?max(S?xv?,0)， ∞ ? max ? ( y v ? T , 0 ) \infty*\max(y_v-T,0) ∞?max(yv??T,0)，实际上这也是在框定x v , y v x_v,y_v xv?,yv? 的范围。
y v ≤ λ y_v\le \lambda yv?≤λ 即T ? S ≤ λ T-S\le \lambda T?S≤λ，权值为∞ ? max ? ( T ? S ? λ , 0 ) \infty*\max(T-S-\lambda,0) ∞?max(T?S?λ,0)
于是我们相当于是要最小化：
∑ v c v ? max ? ( x v ? y v + t v , 0 ) + ∞ ? max ? ( x v ? y v , 0 ) + ∞ ? max ? ( S ? x v , 0 ) + ∞ ? max ? ( y v ? T , 0 ) + ∑ ( u , v ) ∈ E ∞ ? max ? ( y u ? x v , 0 ) + ∞ ? max ? ( T ? S ? λ , 0 ) \sum_v c_v*\max(x_v-y_v+t_v,0)+\infty*\max(x_v-y_v,0)+\infty*\max(S-x_v,0)+\infty*\max(y_v-T,0)\\ +\sum_{(u,v)\in E}\infty*\max(y_u-x_v,0)\\ +\infty*\max(T-S-\lambda,0) v∑?cv??max(xv??yv?+tv?,0)+∞?max(xv??yv?,0)+∞?max(S?xv?,0)+∞?max(yv??T,0)+(u,v)∈E∑?∞?max(yu??xv?,0)+∞?max(T?S?λ,0)
对比LP费用流的形式即可得出要建的边。
此时跑出的最大费用循环流的费用就是要求的最小值。
观察这个图，每个最大费用的循环流相当于是从S S S 出发，走到T T T，然后回到S S S，产生一些费用。
原问题相当于想要最小化λ \lambda λ，使得最大费用循环流 ≤ w \le w ≤w，假设除了T T T 到S S S 的边流i i i 的流量的费用是f i f_i fi?，那么真实的费用是f i ? i λ f_i-i\lambda fi??iλ，于是就是最小化λ \lambda λ，使得max ? ( f i ? i λ ) ≤ w \max(f_i-i\lambda)\le w max(fi??iλ)≤w。
即对于任意的i i i，都要满足λ ≥ f i ? w i \lambda\ge \frac {f_i-w}i λ≥ifi??w?，即找到最大的f i ? w i \frac {f_i-w}i ifi??w?
这个可以表示为平面上( i , f i ) (i,f_i) (i,fi?) 与( 0 , w ) (0,w) (0,w) 的最大斜率，f i f_i fi? 的图像是个凸包，最大值一定在端点取到，所以多路增广是OK的。
