$#C231025B. 图论(graph)
标签（Label）
- 传递闭包
- 深搜
- 时间换空间
- 分块
网址（Website）
题目描述（Problem）
小 $A$ 有一张 $n$ 个点 $m$ 条边的有向无环图，每个点有一个点权，初始均为 $0$。
你需要帮他进行 $q$ 次操作，每次操作可能是以下三种操作中的一种：
$1\ u \ x$：给出 $u, x$，表示将 $u$ 点能到达的点的点权全部改成 $x$ 。
$2 \ u \ x$：给出 $u, x$，表示将 $ u $ 点能到达的点的点权全部和 $x$ 取 $min$。
$3 \ u$ ：给出 $u$，询问 $u$ 点当前的点权。
输入格式
输入文件 $graph.in$包含 $1+m+q$ 行。
第 $1$ 行输入三个正整数依次表示 $n, m, q$。
接下来 $m$ 行每行输入两个正整数 $u, v$，表示一条 $u$ 到 $v$ 的有向边。
接下来 $q$ 行，每行先输入一个编号表示操作种类，再输入相应的 $u, x$ 或者相应的 $u$ 。
输出格式
输出文件 $graph.out$包含若干行，对于每个编号为 $3$ 的操作，输出一行一个非负整数表示答案。
样例
见选手文件
数据规模与约定
对于 $100%$ 的数据：$1≤n, m, q ≤ 5×10^4$ ；$1≤x＜1×10^4$，保证输入会形成一张有向无环图。
| 测试点编号 | $n,m,q$ | 特殊性质 | 空间限制 |
|---|---|---|---|
| $1\sim 4$ | $\le 5\times 10^3$ | 无 | $512M$ |
| $5\sim 6$ | $\le 5\times 10^4$ | 没有操作 $1$ | $512M$ |
| $7\sim 12$ | $\le 5\times 10^4$ | 没有操作 $2$ | $512M$ |
| $13\sim 16$ | $\le 5\times 10^4$ | 无 | $512M$ |
| $17\sim 20$ | $\le 5\times 10^4$ | 无 | $256M$ |
算法分析
以下分析均假定 $n,m,q$ 同阶。
算法一
预处理出每个点能到哪些点，每次修改时依次暴力修改。时间复杂度 $O(n^2)$ ，期望得分 $20$ 分。若没有操作 $1$ ，所有点权始终为 $0$ ，特判这类测试点，期望得分 $30$ 分。
算法二
考虑修改操作对之后每次询问的影响，不难发现，当询问 $u$ 的点权时，往前找到最后一次能影响到 $u$ 的赋值操作，再将这个赋值操作之后的所有能影响到 $u$ 的取 $min$ 操作拿出来，对修改权值一起求个最小值就是答案。
于是可以先用 $bitset$ 预处理传递闭包，将所有的修改操作存在栈里，询问时在栈中找出所有有影响的操作，计算出点权。当栈的大小达到 $O(\sqrt{n})$ 时，将栈中所有操作依次暴力执行并将栈清空即可，时间复杂度 $O(\frac{n^2}{w} + n\sqrt{n})$ ，根据实现时占用的空间，期望得分 $80$ 到 $100$ 分。
如果最后两个测试点空间不够，可以考虑拿时间换空间，第一次选出 $\frac{n}{k}$ 个点，只回答它们的询问，那么预处理传递闭包时也只需要记录每个点能否到达这 $\frac{n}{k}$ 个点，这样做 $k$ 次，每次将 $bitset$ 的空间拿来重复利用即可。时间复杂度乘了 $k$ ，空间复杂度除以了 $k$ 。$k$ 的具体值可以根据自己的代码测试调整，对本题数据选 $k=2,3$ 是比较合适的。期望得分 $100$ 分。
代码（Code）
我的代码
//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的代码
$\qquad$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;
}
