最小費用流與線性規劃

最小費用流問題可以考慮看成一個線性規劃問題。

設 \(f_{u，v}\) 為邊的流量，\(c_{u,v}\) 表示邊的容量，\(w_{u,v}\) 表示邊的代價。\(V\) 表示點集，\(E\) 表示邊集，記總的流量為 \(F\)。

那么最小費用流問題等價于：

• 求 \(\min\{ \sum f_{u,v}w_{u,v} \}\)
• 限制：
• • 對所有 \(u\in V\)，有：
    \[ \sum\limits_{(v,u)\in E}f_{v,u}-\sum\limits_{(u,v)\in E}f_{u,v}=\begin{cases} F,if\ u=n\\ -F,if\ u=1\\ 0,otherwise \end{cases} \]

• • 對所有 \((u,v)\in E\)，有 \(0\le f_{u,v}\le c_{u,v}\)。
• 共 \(m\) 個變量 \(f_{u,v}\)，\(n+m\) 條限制。

給出線性規劃一般形式和其對偶問題：

原問題：

對偶問題：

這里 \(A,x,b,c,y\) 均為矩陣，其中 \(A\) 為 \(n\times m\) 矩陣，\(x,c\) 為 \(n\times 1\) 矩陣，\(y,b\) 為 \(m\times 1\) 矩陣。定義矩陣之間的 \(\le\) 為對應位置都需要小于。

不加證明的給出以下定理：

• 線性規劃和其對偶線性規劃等價。

這里不給證明的原因是該定理證明較為繁雜，博主不會證明，且本博客內容與該性質內容關系不大。

把最小費用流問題對應線性規劃的限制轉化成一般形式：

其中 \(a_u\) 表示點 \(u\) 應該的流量: \(F,-F\) 或 \(0\)。

把這個線性規劃的對偶形式寫出來，限制一共有 \(2n+m\) 個，考慮前 \(n\) 個限制代表變量為 \(q_i\)，另外 \(n\) 個限制代表變量為 \(e_i\)，后 \(m\) 個限制設為 \(r_{u,v}\)。

考慮前 \(2n\) 個向量與限制的對應關系，對于一個限制來說，顯然我們可以讓 \(q_u\) 來對應 \(+\sum f_{v,u}-\sum f_{u,v}\ge a_i\)，這樣所有 \(f_{v,u}\) 代表的位置會有 \(+q_u\)，\(f_{v,u}\) 代表的位置會有 \(-q_u\)。強烈建議各位讀者畫一個矩陣自己感受一下。

最后化成對偶線性規劃為：

• 求 \(\max\{ \sum a_u q_u-\sum\ a_ue_u-\sum r_{u,v}{w_{u,v}} \}\)
• 限制：
• • 對于所有 \((u,v)\in E\)，有：\(-q_u+q_v+e_u-e_v-r_{u,v}\le w_{u,v}\)
• • \(q_u,e_u,r_{u,v}\ge 0\)
• 一共 \(m\) 條限制。

需要注意在推式子的時候，特別關注一下無入度點和無出度點的的情況，它們也是滿足條件的。

發現所有式子都與 \(q_u-e_u\) 有關，不如設其為 \(d_u\)。以及注意到 \(a_u\) 除了 \(1,n\) 都是 \(0\)，所以線性規劃變成：

• 求 \(\max\{ F(d_n-d_1)-\sum r_{u,v}{c_{u,v}} \}\)
• 限制：
• • 對于所有 \((u,v)\in E\)，有：\(d_v\le d_u+r_{u,v}+w_{u,v}\)
• • \(d_u,r_{u,v}\ge 0\)
• 一共 \(m\) 條限制。

\(d_u\) 依然滿足 \(\ge0\) 的原因是，考慮如果找到了一組滿足條件的 \(d\)，那么把 \(d\) 同加到 \(\ge 0\) 依然滿足條件。

Solution

題目大意：給定 \(n\) 個點 \(m\) 條邊的有向圖，邊權為 \(w\)，可以選擇把一條邊的邊權 \(w_i\) 修改為 \(w_i+a_i\)，\(a_i\) 可以為實數，但是需要滿足 \(a_i\ge 0,\sum a_i\le x\)，有 \(q\) 次詢問，每次給定 \(x\)，詢問修改之后 \(1\) 到 \(n\) 最短路的最大值，每次詢問獨立，無重邊無自環。\(n\le 50,w_i\le 10^6,w\le 10^5\)

關注我們的對偶問題，發現限制如同最短路，而 \(r_{u,v}\) 就像我們給每條邊加上的權值 \(a_i\)。

關注我們對偶線性規劃求的東西，可以令 \(c_{u,v}=1\)，那么現在變成了求 \(\max\{ F(d_n-d_1)-\sum r_{u,v} \}\)，其中后者相當于我們更改的權值總和，設為 \(C\)，同時記 \(D=d_n-d_1\) 設為最短路。

我們把所有有用的 \((C,D)\) 映射到二維平面上，形成的圖形一定是上凸殼，且斜率最大是 \(1\)。并且，凸殼上的拐點一定都是整點。且如果讓 \(a_i\) 都是整數，那么顯然隨著 \(C\) 的增加，\(D\) 要么不變，要么加一，在這個情況下建立凸包，而考慮如果令 \(a_i\) 可以為實數，不難發現凸包不會變化。如圖：

如果令所有 \(a_i\) 都是整數，那么點應該是 \(E,F,G\)，而如果 \(a_i\) 可以為實數，那么點 \(I,J,K\)。

由此可以得出結論，凸包上的所有切線都形如 \(\frac{1}{x}\) 的形式，其中 \(x\) 是整數。

設 \(A(F)=\max_{D,C}\{ FD-C \}\)，設對于給定 \(F\)，有 \(A(F)=FD_F-C_F\)，那么 \(D_F=\frac{A(F)}{F}+\frac{C_F}{F}\)。由此可知，若給定 \(F\) 求 \(A(F)\)，方法即為用 \(\frac{1}{F}\) 去切這個凸包，而切線與 \(x\) 軸的截距為 \(A(F)\)。

原問題等價于給定 \(C\)，要求在凸包上找到 \(x=C\) 與凸殼的交點 \((C,D)\)。考慮所有的 \(F\) 和它們對應的切線在 \(x=C\) 處的值，設為 \(y\)，不難發現有 \(y\ge D\)，且一定存在一個 \(x\)，使得 \(y=D\)，即一條與凸包相切且切點為 \((C,D)\) 的切線。則答案為 \(\min_F\{ \frac{A(F)}{F}+\frac{C}{F} \}\)。

現在唯一的問題是 \(F\) 是可以為實數的，一個方法是可以二分，不過不用這么麻煩。我們其實只用考慮 \(F\) 是整數的情況，這是因為凸包上所有的斜率都形如 \(\frac{1}{x}\)，所有對于凸包上每個點 \((C,D)\)，都存在一個整數 \(F\) 使得斜率為 \(\frac{1}{F}\) 的切線經過這個點。

所以，我們枚舉 \(F\)，通過費用流算出 \(A(F)\)，對于每個詢問，算出 \(\min_F\{ \frac{A(F)}{F}+\frac{C}{F} \}\) 即可。

代碼

int n,m;

struct edge{
    int to,next,w,f;
    inline void Init(int to_,int ne_,int w_,int f_){
        to=to_;next=ne_;w=w_;f=f_;
    }
}li[N*N*2];
int head[N],tail=1,now[N],d[N],s,t,Ans,A[N],ans,Q;
bool vis[N];
queue<int> q;

inline void Add(int from,int to,int w,int f){
    li[++tail].Init(to,head[from],w,f);head[from]=tail;swap(from,to);
    li[++tail].Init(to,head[from],-w,0);head[from]=tail;
}
inline bool spfa(int s){
    while(q.size()) q.pop();
    bool op=0;
    mset(d,INF);mset(vis,0);d[s]=0;q.push(s);vis[s]=1;now[s]=head[s];
    while(q.size()){
        int top=q.front();q.pop();vis[top]=0;
        Next(top){
            int to=li[x].to,f=li[x].f,w=li[x].w;if(!f||d[to]<=d[top]+w)continue;
            d[to]=d[top]+w;if(!vis[to]) vis[to]=1,q.push(to);now[to]=head[to];
        }
    }
    if(d[t]>=INF) return 0;else return 1;
}
inline int dinic(int k,int flow){
    if(k==t) return flow;int rest=flow,x;vis[k]=1;
    for(x=now[k];x&&rest;x=li[x].next){
        int to=li[x].to,f=li[x].f,w=li[x].w;
        if(!f||d[to]!=d[k]+w||(vis[to]&&to!=t)) continue;int val=dinic(to,min(rest,f));
        if(!val) d[to]=INF;li[x].f-=val;li[x^1].f+=val;rest-=val;Ans+=val*w;
    }
    now[k]=x;
    return flow-rest;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);
    rep(i,1,m){
        int from,to;read(from);read(to);int w;read(w);
        Add(from,to,w,1);
    }
    s=1,t=n;
    rep(i,1,n){
        if(!spfa(s)) break;
        ans+=dinic(s,1);
        A[i]=Ans;
    }
    read(Q);
    rep(i,1,Q){
        int x;read(x);
        ld nowans=INF;
        rep(i,1,n){
            if(!A[i]) break;
            cmin(nowans,(ld)(A[i]+x)/(ld)(i));
        }
        printf("%0.7Lf\n",nowans);
    }
    return 0;
}