题解 CF1307G【Cow and Exercise】

· · 题解

CF1307G Cow and Exercise解题报告：

更好的阅读体验

题意

给定一个 n 个点 m 条边的带边权有向图， q 次独立的询问一个非负整数 X ，每次可以支持将若干条边的边权增加任意非负实数值，但是需要保证这些值之和不超过 X ，你要使得 1 到 n 的最短路长度最长。（2\leqslant n\leqslant 50,1\leqslant m\leqslant n(n-1),1\leqslant q\leqslant 10^5）

分析

毒瘤线性规划对偶题，这种题不*3500天理难容/fn/fn/fn。

考虑设 w_{u,v} 为有向边的边权， x_{u,v} 表示有向边 (u,v) 增加的边权， y_u 为 1 到 u 的最短路（注意，这里的 y 类似差分约束中的最短路，源点 1 的 y 值可以大于 0 ），那么可以列出最短路对应的线性规划式：

\begin{cases}\text{maximize}\ y_n-y_1\\y_v\leqslant y_u+(w_{u,v}+x_{u,v})\\x_{u,v}\geqslant 0\\\sum_{u,v}x_{u,v}\leqslant X\end{cases}

根据线性规划拼凑的思想，考虑使用 a_{u,v} 个第二行式子， b_{u,v} 个第三行式子， c 个第四行式子凑出 y_n-y_1 的系数，然后用右边的上界之和代替 y_n-y_1 ，再顺便变一下形：

\begin{cases}\text{maximize}\ y_n-y_1\\a_{u,v}(y_v-y_u)-a_{u,v}x_{u,v}\leqslant a_{u,v}w_{u,v}\\-b_{u,v}x_{u,v}\leqslant 0\\c\sum_{u,v}x_{u,v}\leqslant cX\end{cases}

此时，我们就可以其对偶形式表示出来了。

\begin{cases}\text{minimize}\ \sum_{u,v}w_{u,v}a_{u,v}+cX\\\sum_{v}(a_{u,v}-a_{v,u})=\begin{cases}-1&u=n\\1&u=1\\0&\text{otherwise}\end{cases}\\c-a_{u,v}-b_{u,v}=0\\a_{u,v},b_{u,v},c\geqslant0\end{cases}

由于 b_{u,v} 的限制很少，而 c 要尽量小，所以我们可以直接调整 b_{u,v} 的值使得 c=\max\{a_{u,v}\} 。

这个形式仍然不是很好做，考虑将它变换成费用流的形式，即给 a_{u,v},c 同时乘上流量 flow ：

\begin{cases}\text{minimize}\ \frac{\sum_{u,v}w_{u,v}a_{u,v}+cX}{flow}\\\sum_{v}(a_{u,v}-a_{v,u})=\begin{cases}-flow&u=n\\flow&u=1\\0&\text{otherwise}\end{cases}\\c=\max_{u,v}\{a_{u,v}\}\\a_{u,v}\geqslant0\end{cases}

我们对于原图的边 (u,v,w) 在费用流中建一条边 u\rightarrow v ，容量为 1 ，费用为 w ，这样对于任意一组合法的流量，都会满足上面第二条限制（反之亦然），且其费用 cost=\sum_{u,v}w_{u,v}a_{u,v} 。

而且此时存在一个优美的性质 \max\{a_{u,v}\}=1 ，即 c=1 ，那么最后的答案为：

ans=\max_{flow,cost}\{\frac{cost+X}{flow}\}

我们不可能枚举所有的合法流量组，因此考虑建出 flow 与 cost 对应的凸壳，即所有 y=\frac{1}{flow}x+\frac{cost}{flow} 的凸壳。

我们发现在最小费用最大流不断增广的时候的时候， flow 单调递增，同时根据最小费用最大流的贪心性，也可以发现 \frac{cost}{flow} 是不减的，那么每一次增广结束后的 cost 与 flow 一定不重不漏地构成了凸壳的所有位置。

于是我们建图后跑出凸壳，每次查询的时候枚举凸壳所有位置并取最小值就可以了。

时间复杂度： O(nm^2+qm) 。

代码

#include<stdio.h>
#include<queue>
#include<vector>
#define inf 1000000000
using namespace std;
const int maxn=55,maxm=5005;
int n,m,Q,e,flow,cost;
int start[maxn],to[maxm],then[maxm],limit[maxm],worth[maxm],rev[maxm],dis[maxn],vis[maxn],rec[maxn];
queue<int>q;
vector< pair<int,int> >v;
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y,int z,int w,int r){
    then[++e]=start[x],start[x]=e,to[e]=y,limit[e]=z,worth[e]=w,rev[e]=r;
}
inline void addedge(int x,int y,int z,int w){
    add(x,y,z,w,e+2),add(y,x,0,-w,e);
}
int check(int s,int t){
    for(int i=1;i<=n;i++)
        dis[i]=inf,vis[i]=0;
    while(!q.empty())
        q.pop();
    dis[s]=0,vis[s]=1,q.push(s);
    while(!q.empty()){
        int x=q.front();
        vis[x]=0,q.pop();
        for(int i=start[x];i;i=then[i]){
            int y=to[i];
            if(limit[i]&&dis[y]>dis[x]+worth[i]){
                dis[y]=dis[x]+worth[i],rec[y]=i;
                if(vis[y]==0)
                    vis[y]=1,q.push(y);
            }
        }
    }
    return dis[t]==inf? 0:1;
}
void work(int s,int t){
    int minn=inf;
    for(int i=t;i!=s;i=to[rev[rec[i]]])
        minn=min(minn,limit[rec[i]]);
    flow+=minn;
    for(int i=t;i!=s;i=to[rev[rec[i]]])
        limit[rec[i]]-=minn,limit[rev[rec[i]]]+=minn,cost+=worth[rec[i]]*minn;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,1,z);
    }
    while(check(1,n))
        work(1,n),v.push_back(make_pair(cost,flow));
    scanf("%d",&Q);
    while(Q--){
        int x;
        double ans=1.0*inf;
        scanf("%d",&x);
        for(int i=0;i<v.size();i++)
            ans=min(ans,1.0*(v[i].first+x)/v[i].second);
        printf("%.10lf\n",ans);
    }
    return 0;
}