#C231025B. 图论(graph)

网址

题目详情 - 图论(graph) - Super

题解 - 图论(graph) - Super

题目描述

小有一张个点条边的有向无环图，每个点有一个点权，初始均为。

你需要帮他进行次操作，每次操作可能是以下三种操作中的一种：

：给出，表示将点能到达的点的点权全部改成。

：给出，表示将点能到达的点的点权全部和取。

：给出，询问点当前的点权。

输入格式

输入文件包含行。

第行输入三个正整数依次表示。

接下来行每行输入两个正整数，表示一条到的有向边。

接下来行，每行先输入一个编号表示操作种类，再输入相应的或者相应的。

输出格式

输出文件包含若干行，对于每个编号为的操作，输出一行一个非负整数表示答案。

样例

见选手文件

数据规模与约定

对于的数据：；，保证输入会形成一张有向无环图。

测试点编号		特殊性质	空间限制
		无
		没有操作
		没有操作
		无
		无

算法分析

以下分析均假定同阶。

算法一

预处理出每个点能到哪些点，每次修改时依次暴力修改。时间复杂度，期望得分分。若没有操作，所有点权始终为，特判这类测试点，期望得分分。

算法二

考虑修改操作对之后每次询问的影响，不难发现，当询问 uu 的点权时，往前找到最后一次能影响到 uu 的赋值操作，再将这个赋值操作之后的所有能影响到的取操作拿出来，对修改权值一起求个最小值就是答案。

于是可以先用预处理传递闭包，将所有的修改操作存在栈里，询问时在栈中找出所有有影响的操作，计算出点权。当栈的大小达到时，将栈中所有操作依次暴力执行并将栈清空即可，时间复杂度，根据实现时占用的空间，期望得分到分。

如果最后两个测试点空间不够，可以考虑拿时间换空间，第一次选出个点，只回答它们的询问，那么预处理传递闭包时也只需要记录每个点能否到达这个点，这样做次，每次将的空间拿来重复利用即可。时间复杂度乘了，空间复杂度除以了。k的具体值可以根据自己的代码测试调整，对本题数据选是比较合适的。期望得分分。

代码

我的代码

//This is my code!!!
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long 
inline int input(){int x;return cin>>x,x;}
const int HN = 25123;
const int N = 50123;
const int B = 500;//大约2*O(sqrt(n))的大小,区间处理有点像分块 
bool ST;
#include<vector>
vector<int> ft[N];
bitset<N> vst;//判断当前节点是否被访问过 
int n,m,q,ans[N];

int f[B][N];//当前组对于点x的操作二最小值 
int tmp[N];//临时操作记录 
inline void dfs_min(int x,int group,int col){
	f[group][x]=col;//当前组的x的操作min值为col 
	vst[x]=true;//已访问过 
	for(auto y:ft[x]){
		if(!vst[y]) dfs_min(y,group,col);
	}
} 

bitset<HN> d[N];//d[i][j]表示点i能否影响到j点 
int l,r;
inline void dfs(int x){
	vst[x]=true;
	d[x].reset();
	if(l<=x && x<=r) d[x][x-l]=true;//当前点能到达自己  
	for(auto y:ft[x]){
		if(!vst[y]) dfs(y);
		d[x]=d[x]|d[y];
	}
}

int lst[N];//当前询问的上一次修改点 

inline void dfs_fz(int x,int j){
	vst[x]=true;
	lst[x]=j;
	for(auto y:ft[x]){
		if(!vst[y]) dfs_fz(y,j);
	}
}

int op[N],x[N],y[N];//存储操作 
int bl[N];//分组 
bool ED;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	cin>>n>>m>>q;For(i,1,m){
		int x=input(),y=input();
		ft[x].push_back(y);
	}For(i,1,q){
		op[i]=input();x[i]=input();
		switch(op[i]){case 1: case 2: {y[i]=input();}}
	}
	For(i,1,q){
		bl[i]=(i-1)/B;//注意：区间编号从0开始 
		if(i%B==0){//如果刚好可以被区间整除 
			memset(f[bl[i]],0x3f,sizeof(f[bl[i]]));//设置为极大值 
			vst.reset();
			int cnt=0;//操作2的总个数
			For(j,bl[i]*B+1,i){//处理当前区间所有的操作2 
				if(op[j]==2) tmp[++cnt]=j;
			}
			//优化：按影响最小值排序
			sort(tmp+1,tmp+cnt+1,[&](int a,int b){return y[a]<y[b];});
			//因为大的min一定影响不了小的min  因此可以直接统计出整个区间内所有操作2的min  可以用f存下来 
			For(j,1,cnt){
				if(!vst[x[tmp[j]]])//如果没有被访问过 
					dfs_min(x[tmp[j]],bl[i],y[tmp[j]]);
			}
		} 
	}
	
	For(kkk,1,2){//这个东西就是用来防止超内存的 思想：先处理一部分点的值，再处理另一部分 
		memset(lst,0,sizeof(lst));
		if(kkk^2)  l=1,r=n/2;
		else 	   l=n/2+1,r=n;//设置处理值的区间 
		vst.reset();
		For(i,1,n) if(!vst[i]) dfs(i);//先将每个点能影响到的点跑一遍 时间复杂度O(n) 
		For(i,1,q){
			if(op[i]==3 && l<=x[i] && x[i]<=r){//如果当前操作是3且当前点是要求的点 
				int j;//时间线
				int res;//当前询问的答案
				for(j=i-1;j>bl[i]*B;j--){
					if(op[j]==1 && d[x[j]][x[i]-l]) break;
				}
				if(j>bl[i]*B){
					res=y[j];
					for(j=j+1;j<i;j++){
						if(op[j]==2 && d[x[j]][x[i]-l])
							res=min(res,y[j]); 
					}
				}else{
					j=lst[x[i]];//找到上一次赋值x的区间
					res=y[j];
					int tt=bl[j];
					for(j=j+1;bl[j]==tt;j++){//该区间内操作2对j的影响
						if(op[j]==2 && d[x[j]][x[i]-l])
							res=min(res,y[j]); 
					}
					for(j=tt+1;j<bl[i];j++){
						res=min(res,f[j][x[i]]);
					}
					for(j=bl[i]*B+1;j<i;j++){
						if(op[j]==2 && d[x[j]][x[i]-l])
							res=min(res,y[j]);
					}
				}
				ans[i]=res;
			}
			if(i%B==0){
				vst.reset();
				Rof(j,i,bl[i]*B+1){
					if(op[j]==1 && !vst[x[j]])
						dfs_fz(x[j],j);
				}
			}
		}
	}
	For(i,1,q) if(op[i]==3) cout<<ans[i]<<'\n';
	return 0;
}

cx的代码

cx大佬 的博客网址： Huasushis ‘s Blog

//Instruction: This is the code of Chen Xin, the Submitted by just
//		use it to get better unstanding of this problem , 
//		and offer it to other OL who needed , NO OTHER USE!!!!!!!!!




#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define N 50010
#define HN 25010
int n, m, q;
int u, v;
int op[N], x[N], y[N];
vector<int> g[N];
bitset<HN> d[N];
bool vis[N];
int l, r;
void dfs(int u) {
	vis[u] = 1;
	d[u].reset();
	if (l <= u && u <= r) d[u][u - l] = 1;//当前点能到达自己 
	for (auto i : g[u]) {
		if (!vis[i]) dfs(i);
		d[u] |= d[i];//有我能影响哪些点 
	}
}
int sqn;
int stk[N], top, ans[N];
int lst[N], f[224][N], bl[N], tmp[510], cnt;
void dfsmin(int u, int k, int v) {
	vis[u] = 1;
	f[k][u] = v;//第k组的点u赋值为v 
	for (auto i : g[u]) {
		if (!vis[i]) {
			dfsmin(i, k, v);
		}
	}
}
void dfsfz(int u, int p) {
	vis[u] = 1;
	lst[u] = p;
	for (auto i : g[u]) {
		if (!vis[i]) {
			dfsfz(i, p);
		}
	}
}
int main() { 
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		g[u].emplace_back(v);
	}
	for (int i = 1; i <= q; ++i) {
		scanf("%d%d", op + i, x + i);
		switch (op[i]) {
			case 1: case 2: {scanf("%d", y + i); break;}
		}
	}
	sqn = 500;
	for (int i = 1; i <= q; ++i) {//将每一组的操作2暴力操作 时间复杂度 O(n*sqrt(n)) 
		bl[i] = (i - 1) / sqn;//当前分组 
		if (i % sqn == 0) {//如果当前区间为整 
			memset(vis, 0, sizeof(vis));
			memset(f[bl[i]], 63, sizeof(f[bl[i]]));
			cnt = 0;
			for (int j = bl[i] * sqn + 1; j <= i; ++j) {
				if (op[j] == 2) tmp[++cnt] = j;//记录操作2的时间	 
			}
			//按最小值大小排序（大的最小值一定不会影响到小的最小值取值，作为优化） 
			sort(tmp + 1, tmp + cnt + 1, [&](int a, int b){return y[a] < y[b];});
			for (int j = 1; j <= cnt; ++j) {
				if (!vis[x[tmp[j]]])//如果此时的操作点没被访问过（访问过就说明一定有更小值覆盖，就可以不访问了） 
					//暴力下传操作 这里最多下传 O(sqrt(n)) 次  每次下传最多O(n)复杂度 保证了时间复杂度 
					dfsmin(x[tmp[j]], bl[i], y[tmp[j]]);
			}
		}
	}
	for (int aaa = 0; aaa < 2; ++aaa) {//我也不知道为什么这里要分两组 ---防止区间内存爆炸 
		memset(lst, 0, sizeof(lst));
		if (!aaa) l = 1, r = n / 2;
		else l = n / 2 + 1, r = n;//规定每一组的区间 
		memset(vis, 0, sizeof(vis));
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) dfs(i);//先遍历一遍所有的点 
		}
		for (int i = 1; i <= q; ++i) {//枚举每个操作 
			if (op[i] == 3 && l <= x[i] && x[i] <= r) {//如果是询问 
				int j;
				int res;
				for (j = i - 1; j > bl[i] * sqn; --j) {//在当前询问所在的区间内查找 
					if (op[j] == 1 && d[x[j]][x[i] - l]) break;//找到第一个能影响到当前询问的修改点 
				}
				if (j > bl[i] * sqn) {//如果找到了 
					res = y[j];//将当前询问赋值 
					for (j = j + 1; j < i; ++j) {//寻找能影响到当前点的min值 
						if (op[j] == 2 && d[x[j]][x[i] - l]) {
							res = min(res, y[j]);
						}
					}
				} else {//找不到 
					j = lst[x[i]];//找到上一个区间里的最新的赋值操作 
					res = y[j];//赋值颜色 
					int tt = bl[j];//上一个赋值操作的 区间的编号 
					for (j = j + 1; bl[j] == tt; ++j) {//在上一个赋值操作的 区间内寻找能影响x的min操作 
						if (op[j] == 2 && d[x[j]][x[i] - l]) {//能影响到x 
							res = min(res, y[j]);
						}
					}
					for (int j = bl[i] * sqn + 1; j < i; ++j) {//在当前区间内寻找能影响到x的操作2 
						if (op[j] == 2 && d[x[j]][x[i] - l]) {//当前区间的取min操作 
							res = min(res, y[j]);
						}
					}
					for (j = tt + 1; j < bl[i]; ++j) {//找到每个区间能影响到x的操作2的最小值 
						res = min(res, f[j][x[i]]);
					}
				}
				ans[i] = res;
			}
			if (i % sqn == 0) {//开始处理每个区间 
				memset(vis, 0, sizeof(vis));
				for (int j = i; j > bl[i] * sqn; --j) {
					if (op[j] == 1 && !vis[x[j]]) {//倒着寻找最新的区间 
						dfsfz(x[j], j);//开始赋值 
					}
				}
			}
		}
	}
	for (int i = 1; i <= q; ++i) {
		if (op[i] == 3) {
			printf("%d\n", ans[i]);
		}
	}
	return 0;
}

题解代码

#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<bitset>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N=5e4+10;
const int M=25000;
const int B=450;
int n,m,q,to[N],nxt[N],head[N],op[N],x[N],y[N],bl[N],f[130][N],tmp[N],vis[N],tim,hd,tl,val[N],idx[N],ans[N];
bitset<M>F[N];
bool cmp(int i,int j){return y[i]<y[j];}
void cover(int u,int v,int *dp,int t){
	if(vis[u]==tim)return;vis[u]=tim;dp[u]=v;idx[u]=t;
	for(int e=head[u];e;e=nxt[e])cover(to[e],v,dp,t);
}
void getset(int u){
	if(vis[u]==tim)return;vis[u]=tim;
	F[u].reset();if(u>=hd&&u<=tl)F[u][u-hd]=1;
	for(int e=head[u];e;e=nxt[e])getset(to[e]),F[u]|=F[to[e]];
}
int main(){
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	n=gi();m=gi();q=gi();
	for(int i=1,u;i<=m;++i)nxt[i]=head[u=gi()],head[u]=i,to[i]=gi();
	for(int i=1;i<=q;++i){
		op[i]=gi();x[i]=gi();bl[i]=(i-1)/B+1;
		if(op[i]<=2)y[i]=gi();
	}
	for(int i=1;i<=q;++i)
		if(bl[i]^bl[i+1]){
			memset(f[bl[i]],63,sizeof(f[bl[i]]));int len=0;
			for(int j=i;bl[j]==bl[i];--j)if(op[j]==2)tmp[++len]=j;
			sort(tmp+1,tmp+len+1,cmp);++tim;
			for(int j=1;j<=len;++j)cover(x[tmp[j]],y[tmp[j]],f[bl[i]],0);
		}
	for(hd=1,tl=min(n,M);hd<=n;hd=tl+1,tl=min(n,hd+M-1)){
		memset(val,0,sizeof(val));memset(idx,0,sizeof(idx));
		++tim;for(int i=1;i<=n;++i)getset(i);
		for(int i=1,len=0;i<=q;++i)
			if(op[i]==1){
				tmp[++len]=i;
				if(len==B){
					++tim;
					while(len)cover(x[tmp[len]],y[tmp[len]],val,tmp[len]),--len;
				}
			}else if(op[i]==3&&x[i]>=hd&&x[i]<=tl){
				int res=val[x[i]],l=idx[x[i]]+1,r=i-1;
				for(int j=len;j;--j)
					if(F[x[tmp[j]]][x[i]-hd]){
						res=y[tmp[j]];l=tmp[j]+1;break;
					}
				if(l>r);
				else if(bl[l]==bl[r]){
					for(int j=l;j<=r;++j){if(op[j]==2&&F[x[j]][x[i]-hd])res=min(res,y[j]);}
				}
				else{
					for(;bl[l]==bl[l-1];++l)if(op[l]==2&&F[x[l]][x[i]-hd])res=min(res,y[l]);
					for(;bl[r]==bl[r+1];--r)if(op[r]==2&&F[x[r]][x[i]-hd])res=min(res,y[r]);
					for(int j=bl[l];j<=bl[r];++j)res=min(res,f[j][x[i]]);
				}
				ans[i]=res;
			}
	}
	for(int i=1;i<=q;++i)if(op[i]==3)printf("%d\n",ans[i]);return 0;
}