CF1558E Down Below （题解）
Leap_Frog
·
·
题解
Link.
Codeforces
Luogu
P.S.
upd on 9.23 ： 更新了一点笔误。
题解一血 get。
无向图边不开双倍空间 WA 一次。
最大值开了 10^9 不是 10^9+1 WA 一次。
Description.
给定一张无向图 G，除了 1 节点每个节点有两个权值 a_i,b_i。
你初始在 1 节点，有一个权值 val，你可以从 u 移动到 v 当且仅当：
-
u,v\in G
- 你当前的 val>a_v
- 如果这不是第一次移动，移动到 u 前的一个节点不能是 v
移动了之后，val\leftarrow val+b_v。
你可以重复经过一个点，但是你无法重复获得 b 的加成。
你需要经过所有的点，问你初始 val 至少是多少
Solution.
首先必然二分转化成判定性问题。
接下来，我们需要从 1 节点出发，遍历整张图。
有一个经典的套路是维护当前区间所有可以走到的点。
如果没有第三个限制，可以直接用 priority_queue 优先取 a 最小的，复杂度是 O(n\log n\log v)。
可是，如果有第三个限制怎么办呢。
我们仍然维护当前可以走到的点集 S，不过定义改一下。
使得 $x,y\not\in S;u,v,a_i\in S$。
如果当前集合中的点两两可达，这样比较方便维护。
我们需要扩充这个集合，使得它仍然满足两两可达。
不难发现，所有的方案必然只有两种：
1. 起点和终点都属于当前集合
2. 它走到了另一个环，在那边转了一圈后回到这里。
然后就相当于维护一个队列，BFS 向外走。
如果两个不同的起点撞到同一个点，那就是第 $1$ 种情况。
如果两个相同的起点撞到同一个点，就是第 $2$ 种情况。
如果撞到了，那就暴力把这整条路径加上。
可以发现单次复杂度是 $O(n\times m)$ 的，总复杂度是 $O(nm\log v)$ 的。
### Coding.
```cpp
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}/*}}}*/
int n,m,a[1005],b[1005],ls[1005];ll ds[1005];char fg[1005],v[1005];
struct edge{int to,nxt;}e[4005];int et,head[1005];
inline void adde(int x,int y) {e[++et]=(edge){y,head[x]},head[x]=et;}
inline char chk(ll w)
{
fg[1]=1;for(int i=2;i<=n;i++) fg[i]=0;
while(1145141919810)
{
for(int i=1;i<=n;i++) v[i]=fg[i],ls[i]=0,ds[i]=0;
queue<int>q;for(int i=1;i<=n;i++) if(fg[i]) q.push(i),ds[i]=w;
int X=0,Y=0;while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;if(fg[x]&&fg[y]) continue;
if(ds[x]<=a[y]||y==ls[x]) continue;
if(v[y]) {X=x,Y=y;break;}
v[y]=1,ls[y]=x,ds[y]=ds[x]+b[y],q.push(y);
}if(X) break;if(X) break;if(X) break;if(X) break;
}
if(!X) return 0;
for(;!fg[X];X=ls[X]) fg[X]=1,w+=b[X];
for(;!fg[Y];Y=ls[Y]) fg[Y]=1,w+=b[Y];
char qwq=1;for(int i=1;i<=n;i++) qwq&=fg[i];
if(qwq) return 1;
}return '@';
}
inline void solve()
{
read(n,m),et=0,memset(head,0,sizeof(head));int l=1,r=1e9+1,rs=r;
for(int i=2;i<=n;i++) read(a[i]);
for(int i=2;i<=n;i++) read(b[i]);
for(int i=1,x,y;i<=m;i++) read(x,y),adde(x,y),adde(y,x);
while(l<=r) {int md=(l+r)>>1;if(chk(md)) rs=md,r=md-1;else l=md+1;}
printf("%d\n",rs);
}
int main() {int Ca;for(read(Ca);Ca--;) solve();return 0;}
```