CF1307G

Posted on

题目链接

题意：

给出一个 \(n\) 个点 \(m\) 条边的有向图，每条边有边权 \(w_i\) 。

有 \(Q\) 次询问，每次询问给出一个 \(x\) 。你可以把一条边修改成 \(w_i+a_i\) （\(a_i\) 不一定是整数），不过需要保证 \(a_i \geq 0\) 且 \(\sum a_i \leq x\) 。

你要通过修改边权使得从 \(1\) 到 \(n\) 的最短路径尽可能长，每次询问之间独立。

数据保证至少存在一条从 \(1\) 到 \(n\) 的路径，无重边自环。

输出答案和标准答案的相对误差或绝对误差应不超过 \(10^{-6}\) 。(翻译来自luogu)

分析

先观察一下费用流的LP：

\(min:z=\sum flow_i \cdot cst_i\)

限制:

$ \[\begin{cases} u=1时:\sum\limits_{i \in out_u}-flow_i=-F\\ u\in[2,n-1]: \sum\limits_{i \in out_u}-flow_i+\sum\limits_{i\in in_u}flow_i=0 \\ u=n时:\sum\limits_{i \in in_u}flow_i=F \\ flow_1 \leq cap_1 \\ flow_2 \leq cap_2 \\ ...... \\ flow_m \leq cap_m \\ \forall i \in [m],flow_i \geq 0 \end{cases}\]

$

转对偶LP：

\(max: z=F(y_n-y_1)+\sum\limits_{i=1}^{m}y_{n+i}\cdot cap_i\)

限制:

\(\begin{cases} \forall (v,u) \in E:y_u-y_v+y_{n+i} \leq cst_i \\ \forall i \in [n+1,n+m] ,y_{i}\leq 0\end{cases}\)

因而令\(\forall i \in [n+1,n+m], x_{i-n}=-y_i\)

对偶LP为： \(max: z'=F(y_n-y_1)-\sum x_i\) \(\begin{cases} \forall (v,u) \in E:y_u-y_v\leq cst_i+x_i \\ \forall i \in [1,m] ,x_{i}\geq 0\end{cases}\)

很明显，这里的\(y_n-y_1\)就是最短路，整个对偶的LP的限制与题目相符。

令这对LP的最优解的值为\(t\),那么\[F(y_n-y_1)-\sum x_i \leq t\] \[y_n-y_1\leq \frac{t+\sum x_i}{F}\]

因此我们只要求\(\frac{t+\sum x_i}{F}\)的最小值。只要在费用流每次增广的时候几下对应的\((flow,cst)\)，每次询问在这些点里算最小值即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define dow(i,j,k) for(i=j;i>=k;--i)
#define pr pair
#define mkp make_pair
#define fi first
#define se second
const int N=60;
const int M=N*N+N;
namespace MCMF{
    struct edge{
        int nxt,to,w,c;
    }e[M<<1];
    int head[N],pos=1,s,t,dis[N],pre[N],ep[N],flow,cst;
    bool vis[N];
    vector<pr<int,int> >rec;
    void add(int u,int v,int w,int c){
        e[++pos]=(edge){head[u],v,w,c};head[u]=pos;
    }
    bool spfa(){
        int i;rep(i,1,t)dis[i]=1<<30;
        queue<int>q;
        memset(vis,0,sizeof(vis));
        rep(i,1,t)pre[i]=-1;
        dis[s]=0;vis[s]=1;
        q.push(s);
        while(!q.empty()){
            int u=q.front();q.pop();vis[u]=0;
            for(i=head[u];i;i=e[i].nxt)if(e[i].w>0 && dis[e[i].to]>dis[u]+e[i].c){
                    dis[e[i].to]=dis[u]+e[i].c;ep[e[i].to]=i;
                    pre[e[i].to]=u;if(!vis[e[i].to])q.push(e[i].to);vis[e[i].to]=1;
                }
        }
        return dis[t]<(1<<30);
    }
    void EK(){
        int i;
        while(spfa()){
            int f=1<<30;
            for(i=t;i!=s;i=pre[i])
                f=min(f,e[ep[i]].w);
            flow+=f;cst+=f*dis[t];
            for(i=t;i!=s;i=pre[i])e[ep[i]].w-=f,e[ep[i]^1].w+=f;
            rec.push_back(mkp(flow,cst));
        }
    }
}
int n,m,u[M],v[M],w[M];
int solve(int F){
    MCMF::pos=1;
    memset(MCMF::head,0,sizeof(MCMF::head));
    int i,j;
    rep(i,1,m){
        MCMF::add(u[i],v[i],1,w[i]);
        MCMF::add(v[i],u[i],0,-w[i]);
    }
    MCMF::s=n+1;MCMF::t=n+2;
    MCMF::add(n+1,1,F,0);MCMF::add(1,n+1,0,0);
    MCMF::add(n,n+2,F,0);MCMF::add(n+2,n,0,0);
    MCMF::flow=0;MCMF::cst=0;
    MCMF::EK();
    if(MCMF::flow^F)return 1000000;return MCMF::cst;
}
int main(){//freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    int i,j;
    cin>>n>>m;
    rep(i,1,m)cin>>u[i]>>v[i]>>w[i];
    int q;
    cin>>q;
    solve(m);

    while(q--){
        int xx;cin>>xx;
        double ans=1e9;
        for(auto v:MCMF::rec)ans=min(ans,(1.0*xx+v.se)/v.fi);
        cout<<fixed;cout<<setprecision(10)<<ans<<'\n';
    }
}