义乌中学暑假集训 2021.07.14 D

(Updated: )
oi
,

给定一个 $n$​ 个节点，$m$ 条边无向图，初始边权均为 $1$。有 $k$ 次操作，每次操作可以选取一条边，使其边权加一。

设一条边的边权为 $v$​​，定义经过该边的时间为 $\frac{1}{v}$​​。

现有两个人，其中一个从 $s_1$ 走到 $t_1$，一个从 $s_2$ 走到 $t_2$，问如何操作使得两人花费总时间最少？

$n,m\leq 5000,0\leq k\leq 10^9$。

Sol

这里给个非正解。

直接分别跑两次最短路，然后记录一下重复路径，再整个三分就过了。

然后简要说说正解。

显然两人重复路径一定是连续的一条。

那么肯定是一条长链+四条链挂在端点上。

暴力枚举长链的两个端点，然后处理出每个点到起始点/终点的距离（四条链），然后丢到一个桶里。

现在你就可以知道重复路径为长度为 $i$ 时，四条链长度最小值。

然后对于所有的 $i$ 分别跑次三分就好了。

这里给出非正解代码：

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
#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define LL long long
using namespace std;
#define double long double
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(int x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=5e3+10;
int n,m,k,fir[N],nxt[N<<1],son[N<<1],w[N<<1],tot=1,s1,t1,s2,t2,F[N],vis[N],p[N],Sum,A1,A2,GG[N];
vector<int> g[N];
I void Add(CI x,CI y){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y;}
#define to son[i] 
queue<int> q;
I void Spfa(){
    RI u,i;W(!q.empty()) q.pop();memset(F,63,sizeof(F)),memset(vis,0,sizeof(vis)),vis[s1]=1,F[s1]=0,q.push(s1);W(!q.empty())
        for(u=q.front(),q.pop(),i=fir[u];i;i=nxt[i]) if(F[to]>F[u]+1) g[to].clear(),g[to].push_back(i),F[to]=F[u]+1,!vis[to]&&(q.push(to),vis[to]=1);
        else if(F[to]==F[u]+1) g[to].push_back(i);
    return ;
}
I void U(CI x){if(x==s1) return ;RI i,sz=g[x].size();for(i=0;i<sz;i++) w[g[x][i]]++,w[g[x][i]^1]++,!GG[son[g[x][i]^1]]&&(GG[son[g[x][i]^1]]=1,U(son[g[x][i]^1]),0);}
I void Spfa2(){
    RI u,i;W(!q.empty()) q.pop();memset(F,63,sizeof(F)),memset(vis,0,sizeof(vis)),vis[s2]=1,F[s2]=0,q.push(s2);W(!q.empty())
        for(u=q.front(),q.pop(),i=fir[u];i;i=nxt[i]) if(F[to]>F[u]+1) p[to]=i,F[to]=F[u]+1,!vis[to]&&(q.push(to),vis[to]=1);
        else if(F[to]==F[u]+1&&w[i]&&!w[p[to]]) p[to]=i;
    return ;
}
I void U2(CI x){if(x==s2) return ;Sum+=(w[p[x]]>0),U2(son[p[x]^1]);}
I double Q(CI x,CI y,CI z){
    if(k<=z) return 0.0+x+y-2.0*z+(z-k)*2.0+k;
    if(!(x+y-z)) return 0.0;
    RI t=k/(x+y-z);t++;k%=(x+y-z);
    if(k>z) return 1.0*(x+y-2*z-(k-z))*(1.0/t)+1.0*(k-z)*(1.0/(t+1))+2.0*z*(1.0/(t+1));
    return 1.0*(x+y-2*z)*(1.0/t)+2.0*(z-k)*(1.0/t)+2.0*k*(1.0/(t+1));
}
I double check(int x,int y,int mid){
    RI f=mid/y,g=(k-mid)/x;++f,++g;
    return (1.0-1.0/f)*y*2+(2.0*(mid%y)/f/(f+1))
            +(1.0-1.0/g)*x+(1.0*((k-mid)%x)/(g+1)/g);
}
I double calc(int x,int y){
    if(!x&&!y) return 0;
    if(!x){
        RI f=k/y;++f;
        return 2*y-(f?(1.0-1.0/f)*y*2:0)-(k%y)*(2.0/f/(f+1));
    }
    if(!y){
        RI g=k/x;++g;
        return x-(g?(1.0-1.0/g)*x:0)-(k%x)*(1.0/g/(g+1));
    }
    int l=0,r=k,i;
    while(r-l>=3){
        RI lmid=l+(r-l)/3,rmid=lmid+(r-l)/3;
        if(check(x,y,lmid)<check(x,y,rmid)) l=lmid;
        else r=rmid;
    }
    double res=0;
    for(i=l;i<=r;i++) res=max(res,check(x,y,i));
    return x+2*y-res;
}
int main(){
    RI i,x,y;for(read(n),read(m),read(k),i=1;i<=m;i++) read(x),read(y),Add(x,y),Add(y,x);
    return read(s1),read(t1),read(s2),read(t2),Spfa(),A1=F[t1],U(t1),Spfa2(),A2=F[t2],U2(t2),printf("%.17Lf\n",calc(A1+A2-Sum*2,Sum)),0;
}