差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 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
@@ 行 1: / 行 1: @@
-====== Codeforces Round #732 (Div. 1) ======
+====== Codeforces Round #740 (Div. 1) ======
 [[https://codeforces.com/contest/1558|比赛链接]]
@@ 行 109: / 行 109: @@
 	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>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具