2020-2021:teams:legal_string:jxm2001:contest:cf_740_div._1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:cf_740_div._1 [2021/08/25 11:09] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:cf_740_div._1 [2021/08/25 17:46] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 109: | 行 109: | ||
| return 0; | return 0; | ||
| } | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== E. Down Below ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n$ 个点 $m$ 条边无向图。除 $1$ 号点外每个点 $i$ 有一个怪物，玩家能力值大于 $a_i$ 才能击败怪物，击败怪物玩家能力值上升 $b_i$。 | ||
| + | |||
| + | 玩家从 $1$ 号点出发，每条边可以走无限次，但如果玩家上一步是 $u\to v$，则这一步不能是 $v\to u$。 | ||
| + | |||
| + | 玩家只有杀死第 $i$ 个点的怪物才能进入第 $i$ 个点，问玩家的最小初始能力值，使得玩家能否杀死所有怪物。数据保证每个点度数至少为 $2$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 不难想到二分初始能力值，难点在于如何验证答案。 | ||
| + | |||
| + | 考虑维护集合 $S$，对集合 $S$ 的每个点 $u$，玩家都可以从 $1$ 号点出发，杀死 $S$ 集合每个点的怪物后回到 $u$。 | ||
| + | |||
| + | 考虑拓展集合 $S$，可以从集合 $S$ 的任意点 $u$ 出发，进行 $\text{dfs}$，并且不经过所有 $v\in S$ 的点。 | ||
| + | |||
| + | 从 $u$ 出发的可行能力值为初始能力值 $+\sum_{v\in s}b_v$。按照题目规则移动，如果路径出现环，显然这条路径的所有点可以加入 $S$。 | ||
| + | |||
| + | 若存在 $u,v\in S$，$u\to x,v\to x$ 是两条不相交的路径，假定 $u\to x$ 获得的能量不小于 $v\to x$ 获得的能量，则可以将路径 $u\to x\to v$ 加入 $S$。 | ||
| + | |||
| + | 因此每次拓展集合 $S$ 可以暴力对 $S$ 的每个点进行 $\text{dfs}$，其他每个点至多被访问一次，时间复杂度 $O(n+m)$。 | ||
| + | |||
| + | $S$ 最多拓展 $O(n)$ 次，因此验证答案复杂度 $O(nm)$。总时间复杂度 $O(nm\log V)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e3+5,MAXM=2e3+5,inf=1e9+5; | ||
| + | struct Edge{ | ||
| + | int to,next; | ||
| + | }edge[MAXM<<1]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v){ | ||
| + | edge[++edge_cnt]=Edge{v,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int a[MAXN],b[MAXN],f[MAXN],vis[MAXN]; | ||
| + | vector<int> vec; | ||
| + | bool dfs(int u,int fa,LL s){ | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(vis[u]==u&&vis[v]==v)continue; | ||
| + | if(v==fa||a[v]>=s)continue; | ||
| + | if(vis[v]){ | ||
| + | vec.push_back(u); | ||
| + | if(vis[v]!=vis[u]){ | ||
| + | int pos=v; | ||
| + | while(pos&&vis[pos]!=pos){ | ||
| + | vec.push_back(pos); | ||
| + | pos=f[pos]; | ||
| + | } | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | vis[v]=vis[u]; | ||
| + | f[v]=u; | ||
| + | if(dfs(v,u,s+b[v])){ | ||
| + | if(vis[u]!=u) | ||
| + | vec.push_back(u); | ||
| + | return true; | ||
| + | } | ||
| + | } | ||
| + | return false; | ||
| + | } | ||
| + | bool check(int n,int k){ | ||
| + | vec.clear(); | ||
| + | vec.push_back(1); | ||
| + | bool flag=true; | ||
| + | while(flag){ | ||
| + | flag=false; | ||
| + | LL s=k; | ||
| + | _rep(u,1,n) | ||
| + | vis[u]=0; | ||
| + | for(int u:vec){ | ||
| + | vis[u]=u; | ||
| + | s+=b[u]; | ||
| + | } | ||
| + | for(int u:vec){ | ||
| + | if(dfs(u,0,s)){ | ||
| + | flag=true; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | return vec.size()==n; | ||
| + | } | ||
| + | void solve(){ | ||
| + | int n=read_int(),m=read_int(); | ||
| + | _rep(i,2,n) | ||
| + | a[i]=read_int(); | ||
| + | _rep(i,2,n) | ||
| + | b[i]=read_int(); | ||
| + | _rep(i,1,n)head[i]=0; | ||
| + | edge_cnt=0; | ||
| + | while(m--){ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | Insert(u,v); | ||
| + | Insert(v,u); | ||
| + | } | ||
| + | int lef=1,rig=inf,ans=inf; | ||
| + | while(lef<=rig){ | ||
| + | int mid=lef+rig>>1; | ||
| + | if(check(n,mid)){ | ||
| + | ans=mid; | ||
| + | rig=mid-1; | ||
| + | } | ||
| + | else | ||
| + | lef=mid+1; | ||
| + | } | ||
| + | enter(ans); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int T=read_int(); | ||
| + | while(T--) | ||
| + | solve(); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_740_div._1.1629860962.txt.gz · 最后更改: 2021/08/25 11:09 由 jxm2001
