Solution - CF160D Edges in MST

Posted on Edited on

CF160D Edges in MST

退役后没事干写的。

首先，有个比较好想的暴力做法：先随便找一个最小生成树，然后树剖+线段树维护,每次对于横插边，看看链上边权的最大值是否和当前边权相等，如果相等是 2 否则是 3 ，同时更新这一段链使用横插边替换的最小值。做完横插边以后，对于树边，只需看看该点最小值是否为此边权即可，是即 2 ，不是即 3 。两个 log⁡\log ，但是 n≤105n\leq 10^5 ，所以被我搞过去了（还挺快）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
#define gc getchar
#define pc putchar
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
inline int read(){
	int x=0;char ch=gc();bool p=1;
	while (!isdigit(ch)) ch=='-'?p=0:0,ch=gc();
	while ( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^'0'),ch=gc();
	return p?x:-x;
}
const int N=1e5+5,INF=1e9+7;
struct Edge{
	int pos,val;
};
std::vector<Edge> G[N];
int n,m,dfn[N],dep[N],top[N],fa[N],son[N],sz[N],val[N],tot,vvv[N];
void Dfs0(int cur){
	//printf("cur = %d\n",cur);
	sz[cur]=1;
	dep[cur]=dep[fa[cur]]+1;
	F(i,0,(int)G[cur].size()-1){
		int to=G[cur][i].pos,v=G[cur][i].val;
		if (to==fa[cur]) continue;
		fa[to]=cur;
		vvv[to]=v;
		Dfs0(to);
		sz[cur]+=sz[to];
		if (sz[to]>sz[son[cur]]) son[cur]=to;
	}
}
void Dfs1(int cur){
	dfn[cur]=++tot;//printf("cur = %d, fa = %d, dfn = %d\n",cur,fa[cur],dfn[cur]);
	val[dfn[cur]]=vvv[cur];
	if (!top[cur]) top[cur]=cur;
	if (son[cur]) top[son[cur]]=top[cur],Dfs1(son[cur]);
	F(i,0,(int)G[cur].size()-1){
		int to=G[cur][i].pos;
		if (to==fa[cur]||to==son[cur]) continue;
		Dfs1(to);
	}
}
#define min std::min
#define max std::max
#define mid ((l+r)>>1)
int lz[N<<2],minn[N<<2],maxn[N<<2];
inline void pushup(int k){
	minn[k]=min(minn[k<<1],minn[k<<1|1]);
}
inline void putmin(int k,int v){
	minn[k]=min(minn[k],v),lz[k]=min(lz[k],v);
}
inline void pushdown(int k){
	if (lz[k]!=INF) putmin(k<<1,lz[k]),putmin(k<<1|1,lz[k]),lz[k]=INF;
}
void Build(int k,int l,int r){
	lz[k]=INF;
	if (l==r) return minn[k]=INF,maxn[k]=val[l],void();
	Build(k<<1,l,mid),Build(k<<1|1,mid+1,r);
	pushup(k);maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
}
void Modify(int k,int l,int r,int le,int ri,int v){
	if (l>=le&&r<=ri) return putmin(k,v);
	pushdown(k);
	if (mid>=le) Modify(k<<1,l,mid,le,ri,v);
	if (mid< ri) Modify(k<<1|1,mid+1,r,le,ri,v);
	pushup(k);
}
int Querymax(int k,int l,int r,int le,int ri){
	if (l>=le&&r<=ri) return maxn[k];
	int res=0;pushdown(k);
	if (mid>=le) res=max(res,Querymax(k<<1,l,mid,le,ri));
	if (mid< ri) res=max(res,Querymax(k<<1|1,mid+1,r,le,ri));
	return res;
}
int Querymin(int k,int l,int r,int pos){
	if (l==r) return minn[k];
	pushdown(k);
	if (mid>=pos) return Querymin(k<<1,l,mid,pos);
	else return Querymin(k<<1|1,mid+1,r,pos);
}
inline bool Add(int x,int y,int v){
	//printf("Add:: x = %d, y = %d, v = %d\n",x,y,v);
	std::vector<Edge> p;
	while (top[x]!=top[y]){
		//printf("x = %d, y = %d\n",x,y);
		if (dep[top[x]]<dep[top[y]]) x^=y^=x^=y;
		p.push_back({dfn[top[x]],dfn[x]});
		x=fa[top[x]];
	}
	if (x!=y){
		if (dep[x]<dep[y]) x^=y^=x^=y;
		p.push_back({dfn[y]+1,dfn[x]});
	}
	bool flag=0;
	F(i,0,(int)p.size()-1){
		int l=p[i].pos,r=p[i].val;
		//printf("now = %d %d, ans = %d\n",l,r,Querymax(1,1,n,l,r));
		Modify(1,1,n,l,r,v);
		if (Querymax(1,1,n,l,r)==v) flag=1;
	}
	return flag;
}
struct eee{
	int l,r,val,tag;
} w[N];
inline bool operator < (eee a,eee b){
	return a.val<b.val;
}
int f[N];
inline int find(int x){
	if (x==f[x]) return x;
	return f[x]=find(f[x]);
}
int ans[N];
signed main(){
	n=read(),m=read();
	F(i,1,n) f[i]=i;
	F(i,1,m){
		w[i].l=read(),w[i].r=read(),w[i].val=read(),w[i].tag=i;
	}
	std::sort(w+1,w+1+m);
	F(i,1,m){
		int x=w[i].l,y=w[i].r,v=w[i].val;
		//printf("findx = %d, findy = %d\n",find(x),find(y));
		if (find(x)==find(y)) continue;
		f[find(x)]=find(y);
		G[x].push_back({y,v});
		G[y].push_back({x,v});
		//printf("add %d and %d\n",x,y);
	}
	//system("pause");
	Dfs0(1),Dfs1(1);
	Build(1,1,n);
	//F(i,1,n) printf("i = %d, dfn = %d\n",i,dfn[i]);
	F(i,1,m){
		int x=w[i].l,y=w[i].r,v=w[i].val;
		if (fa[x]!=y&&fa[y]!=x){
			ans[w[i].tag]=Add(x,y,v)?2:3;
		}
	}
	F(i,1,m){
		int x=w[i].l,y=w[i].r;
		if (fa[x]==y||fa[y]==x){
			if (dep[x]<dep[y]) x^=y^=x^=y;
			if (Querymin(1,1,n,dfn[x])==Querymax(1,1,n,dfn[x],dfn[x])) ans[w[i].tag]=2;
			else ans[w[i].tag]=1;
			//printf("x = %d, y = %d, Qmin = %d, Qmax = %d\n",x,y,
			//Querymin(1,1,n,dfn[x]),Querymax(1,1,n,dfn[x],dfn[x]));
		}
	}
	F(i,1,m){
		if (ans[i]==1) puts("any");
		else if (ans[i]==2) puts("at least one");
		else puts("none");
	}
	return 0;
}

一查题解发现有个比较聪明的做法。对于边权相同的情况，显然就是割边为 1 ，否则为 2 。那么就做 kruskal 的时候把边权相同的边一起考虑， Tarjan 判断割边就好啦。这个玩意只有一只 log⁡\log ，还好写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
#define gc getchar
#define pc putchar
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
inline int read(){
	int x=0;char ch=gc();
	while (!isdigit(ch)) ch=gc();
	while ( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^'0'),ch=gc();
	return x;
}
const int N=1e5+5;
int n,m;
struct Edge{
	int l,r,val,tag;
} P[N];
inline bool operator < (Edge a,Edge b){
	return a.val<b.val;
}
struct node{
	int pos,tag;
};
std::vector<node> G[N];
int dfn[N],low[N],tot,fa[N],ans[N];
inline int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
#define min std::min
void Tarjan(int cur,int pre){
	dfn[cur]=low[cur]=++tot;
	F(i,0,(int)G[cur].size()-1){
		int to=G[cur][i].pos,tg=G[cur][i].tag;
		if (pre==tg) continue;
		if (!dfn[to]) Tarjan(to,tg),low[cur]=min(low[cur],low[to]);
		else low[cur]=min(low[cur],dfn[to]);
	}
	if (low[cur]==dfn[cur]&&pre) ans[pre]=1;
}
signed main(){
	n=read(),m=read();
	F(i,1,n) fa[i]=i;
	F(i,1,m){
		P[i].l=read(),P[i].r=read(),P[i].val=read(),P[i].tag=i;
	}
	std::sort(P+1,P+1+m);
	F(i,1,m){
		int rr=i;
		while (rr<m&&P[rr+1].val==P[rr].val) ++rr;
		F(j,i,rr){
			int l=find(P[j].l),r=find(P[j].r),tg=P[j].tag;
			if (l==r){
				ans[tg]=3;
				continue;
			}
			G[l].push_back({r,tg});
			G[r].push_back({l,tg});
		}
		F(j,i,rr){
			int l=find(P[j].l),r=find(P[j].r);
			if (l!=r&&!dfn[l]) Tarjan(l,0);
		}
		F(j,i,rr){
			int l=find(P[j].l),r=find(P[j].r),tg=P[j].tag;
			G[l].clear(),G[r].clear();
			dfn[l]=dfn[r]=low[l]=low[r]=0;
			if (!ans[tg]) ans[tg]=2;
		}
		F(j,i,rr){
			int l=find(P[j].l),r=find(P[j].r);
			fa[l]=r;
		}
		i=rr;
	}
	F(i,1,m){
		if (ans[i]==1) puts("any");
		else if (ans[i]==2) puts("at least one");
		else puts("none");
	}
	return 0;
}