CF1558E Down Below

· · 题解

在没有看到不能返回之前我认为这是个简单题。

然而有这一个条件，显然我们每次只能拓展类似于一个环的东西。

首先肯定二分答案，然后我们发现如果能够遍历，那么你每次瞎拓展都行。

也就是说，你随意找环，最后一定能遍历，如果遍历不了，那就是遍历不了。

考虑暴力搜索找环，如果走到了之前走过的点（不同起点也算）那么我们一定可以走回去。所以每次找环每个点只会被经过一次。

注意此处我们其实是无限弱化了条件，但是达到了想要的效果。

所以复杂度为 O(n(n+m)\log V)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
const int N=1005;
#define pb push_back
#define ll long long
vector<int>G[N];
int n,m,T,a[N],b[N],vis[N],flg,pre[N];
inline void tag(int x){for(;x;x=pre[x])vis[x]=1;}
inline void dfs(int x,int las,ll v){
    for(auto t:G[x]){
        if((vis[x]&&vis[t])||(a[t]>=v)||(t==las))continue;
        if(vis[t]){flg=1;tag(x);return;}
        if(pre[t]){flg=1;tag(x),tag(t);return;}
        pre[t]=x;dfs(t,x,v+b[t]);if(flg)return;
    }
}
inline bool chk(int val){
    for(int i=1;i<=n;i++)vis[i]=0;
    vis[1]=1;while(1){
        int cnt=0;ll v=val;
        for(int i=1;i<=n;i++){
            pre[i]=0;
            if(vis[i])++cnt,v+=b[i];
        }if(cnt==n)return 1;flg=0;
        for(int i=1;i<=n&&!flg;i++)
            if(vis[i])dfs(i,0,v);
        if(!flg)return 0;
    }
}
inline void solve(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)G[i].clear();
    for(int i=2;i<=n;i++)a[i]=read();
    for(int i=2;i<=n;i++)b[i]=read();
    for(int i=1,x,y;i<=m;i++)
        x=read(),y=read(),G[x].pb(y),G[y].pb(x);
    int l=1,r=inf+1,ans=r;
    while(l<=r){
        int mid=(l+r)>>1;
        if(chk(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }printf("%d\n",ans);
}
int main(){
    T=read();
    while(T--)solve();
    return 0;
}

深深地感到自己的弱小。