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;
}