差别

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

--- 2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_2 [2023/07/23 14:32]
blackening
+++ 2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_2 [2023/07/23 20:14] (当前版本)
coldwinds
@@ 行 1: / 行 1: @@
 ===A===
 ===B===
+**树剖+线段树+网络流（最大权闭合子图）**
+给定一棵n个节点的树，有边权（维护成本），给定m组顶点，代表一条线路，同时给出了该线路带来的利润。可以删除树上的边，以及放弃若干条线路，求：最大利润。
+问题即求最大权闭合子图。
+建图方式：建立汇点和源点，将源点与m条线路相连，边权为利润，将汇点与树上节点相连，边权为成本，若第i条线路需要经过树上的第j条边，就把线路i和树边j连接，边权为INF。
+最后的答案为：全部利润和-该图最大流
+由于点的数量为1e4，最坏情况有1e8条边，无法直接建图，可以用线段树优化建图。对给出的树进行树链剖分，将每条线路的路径转化为若干连续区间，再使用线段树优化对区间的连边(若区间[L,R]在线段树上用一个节点维护，则直接将边连到改节点，不需要连到叶节点)。优化过的图，点数为5n+m=6e4，边数为5n+m(1+logn)=2e5。
+**AC代码**
+<code>
+#include<bits/stdc++.h>
+using namespace std;
+const int maxn=1e6+5,INF=2e9;
+int n,m,u,v,c,x,y;
+vector<pair<int,int> >ve[maxn];
+int nxt[maxn],to[maxn],head[maxn],val[maxn],cur[maxn];
+int cnt;
+void add_edge(int u,int v,int va){
+	to[cnt]=v;
+	nxt[cnt]=head[u];
+	head[u]=cnt;
+	val[cnt]=va;
+	cnt++;
+}
+int sz[maxn],hson[maxn],fa[maxn],dep[maxn],w[maxn];
+int id[maxn],re[maxn],idx,top[maxn];
+void dfs1(int p,int Fa,int weigh){
+	sz[p]=1;
+	fa[p]=Fa;
+	dep[p]=dep[Fa]+1;
+	w[p]=weigh;
+	int SIZE=ve[p].size();
+	int maxx=0;
+	for(int i=0;i<SIZE;i++){
+		if(ve[p][i].first==Fa)continue;
+		dfs1(ve[p][i].first,p,ve[p][i].second);
+		sz[p]+=sz[ve[p][i].first];
+		if(maxx<sz[ve[p][i].first]){
+			maxx=sz[ve[p][i].first];
+			hson[p]=ve[p][i].first;
+		}
+	}
+}
+void dfs2(int p,int Fa,int t){
+	id[p]=++idx;
+	re[id[p]]=p;
+	top[p]=t;
+	if(hson[p])dfs2(hson[p],p,t);
+	int SIZE=ve[p].size();
+	for(int i=0;i<SIZE;i++){
+		if(ve[p][i].first==Fa||ve[p][i].first==hson[p])continue;
+		dfs2(ve[p][i].first,p,ve[p][i].first);
+	}
+}
+int en;
+void pushup(int rt){
+	add_edge(rt,rt<<1,INF);
+	add_edge(rt<<1,rt,0);
+	add_edge(rt<<1|1,rt,0);
+	add_edge(rt,rt<<1|1,INF);
+}
+void build(int l,int r,int rt){
+	if(l==r){
+		add_edge(rt,en,w[re[l]]);
+		add_edge(en,rt,0);
+		return;
+	}
+	int mid=(l+r)>>1;
+	build(l,mid,rt<<1);
+	build(mid+1,r,rt<<1|1);
+	pushup(rt);
+}
+void query(int l,int r,int L,int R,int va,int rt){
+	if(l>=L&&r<=R){
+		add_edge(va,rt,INF);
+		add_edge(rt,va,0);
+		return;
+	}
+	int mid=(l+r)>>1;
+	if(L<=mid)query(l,mid,L,R,va,rt<<1);
+	if(R>mid)query(mid+1,r,L,R,va,rt<<1|1);
+}
+int dis[maxn];
+bool f[maxn];
+queue<int>qu;
+bool bfs(){
+	memset(dis,0,sizeof(dis));
+	memset(f,0,sizeof(f));
+	dis[0]=1;
+	f[0]=1;
+	qu.push(0);
+	while(!qu.empty()){
+		int fr=qu.front();
+		qu.pop();
+		for(int i=head[fr];i!=-1;i=nxt[i]){
+			if(val[i]>0&&dis[to[i]]==0){
+				dis[to[i]]=dis[fr]+1;
+				if(!f[to[i]]){
+					f[to[i]]=1;
+					qu.push(to[i]);
+				}
+			}
+		}
+	}
+	return dis[en]>0;
+}
+int dfs(int p,int maxflow){
+	if(p==en)return maxflow;
+	int rest=maxflow;
+	for(int i=cur[p];i!=-1&&rest>0;i=nxt[i]){
+		cur[p]=i;
+		if(val[i]>0&&dis[to[i]]==dis[p]+1){
+			int tmp=dfs(to[i],min(rest,val[i]));
+			val[i]-=tmp;
+			val[i^1]+=tmp;
+			rest-=tmp;
+		}
+	}
+	return maxflow-rest;
+}
+int dinic(){
+	int res=0;
+	while(bfs()){
+		int tmp=0;
+		for(int i=0;i<=4*n+m+1;i++)cur[i]=head[i];
+		do{
+			tmp=dfs(0,INF);
+			res+=tmp;
+		}while(tmp>0);
+	}
+	return res;
+}
+int main(){
+	cin>>n>>m;
+	memset(head,-1,sizeof(head));
+	for(int i=1;i<n;i++){
+		cin>>u>>v>>c;
+		ve[v].push_back(make_pair(u,c));
+		ve[u].push_back(make_pair(v,c));
+	}
+	dep[1]=1;
+	dfs1(1,0,0);
+	dfs2(1,0,1);
+	en=4*n+m+1;
+	build(1,n,1);
+	int ans=0;
+	for(int i=1;i<=m;i++){
+		cin>>u>>v>>x>>y;
+		if(x<=y)continue;
+		add_edge(0,4*n+i,x-y);
+		add_edge(4*n+i,0,0);
+		ans+=x-y;
+		while(top[u]!=top[v]){
+			if(dep[top[u]]<dep[top[v]])swap(u,v);
+			query(1,n,id[top[u]],id[u],4*n+i,1);
+			u=fa[top[u]];
+		}
+		if(dep[u]<dep[v])swap(u,v);
+		query(1,n,id[v]+1,id[u],4*n+i,1);
+	}
+	int flow=dinic();
+	cout<<ans-flow<<endl;
+	return 0;
+}
+</code>
 ===C===
 ===D===
@@ 行 126: / 行 297: @@
 		   	for(int j=0;j<m;++j){
 		   	   	if(flag>0){
-		   	   	   	if(count<=4){
+		   	   	   if(count<=4){
-		   	   	   	  	printf("x");
+		   	   	   	  printf("x");
-		   	   	   	  	count++;
+		   	   	   	  count++;
-		   	   	   	}
+		   	   	   }
-		   	   	   	else{
+		   	   	   else{
-		   	   	   	  	count = 1;
+		   	   	   	  count = 1;
-		   	   	   	  	printf("o");
+		   	   	   	  printf("o");
-		   	   	   	}
+		   	   	   }
 		   	   	}
 		   	   	else{
-		   	   	    if(count<=4){
+		   	   	   if(count<=4){
-		   	   	   	  	printf("o");
+		   	   	   	  printf("o");
-		   	   	   	  	count++;
+		   	   	   	  count++;
-		   	   	   	}
+		   	   	   }
-		   	   	   	else{
+		   	   	   else{
-		   	   	   	  	count = 1;
+		   	   	   	  count = 1;
-		   	   	   	  	printf("x");
+		   	   	   	  printf("x");
-		   	   	   	}
+		   	   	   }
 		   	   	}
 		   	}
@@ 行 157: / 行 328: @@
 		}
-    }
+        }
 }
 </code>

CVBB ACM Team

用户工具

站点工具

差别

页面工具