P8519 [IOI2021] 钥匙

,

Description

https://www.luogu.com.cn/problem/P8519

Solution

傻逼锣鼓连个交互库都不发。

观察到如果 $i\to j$，且 $i,j$ 不在一个强联通中，则 $i$ 不会是最小的。

考虑每次把没有出度强联通拿出来搜，如果搜到一个不属于当前集合的点则连边。如果搜完了都没有搜到，那么它就是最后的那个联通块。

每次拿来扩展，想到 B 开头的最小生成树算法。具体就是找到不属于当前集合的点则退出并合并联通块。每个联通块只需要维护没有出度的强联通中的一个点。这样每层遍历是 $O(n)$ 的，每层又会让联通块个数减半，复杂度就是 $O(n\log n)$。

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 300005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m;
int fa[maxn],vis[maxn],fl[maxn],col[maxn];
vector<pair<int,int> >to[maxn];
int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int q[maxn],head,tail;
int Ans[maxn],cnt,ans,keys[maxn],in[maxn],rev[maxn];
vector<int>e[maxn],h;
void clear(void) {
	for (auto tmp:h) e[tmp].clear(),rev[tmp]=0;h.clear();
	for (int i=1;i<=tail;i++) keys[col[q[i]]]=0,vis[q[i]]=0;//,gdb(i,q[i]);
	head=1;tail=0;
}
void bfs(int s) {
	int i,x;
	head=1,tail=0;q[++tail]=s;//keys[col[s]]=1;
	for (i=1;i<=n;i++) gdb(s,i,keys[i]);
	while (head<=tail) {
		x=q[head++];vis[x]=1;
		for (auto tmp:to[x]) if (!vis[tmp.fi]){
			if (keys[tmp.se]) {
				vis[tmp.fi]=1;keys[col[tmp.fi]]=1;q[++tail]=tmp.fi;
				if (getfa(tmp.fi)!=s) return fa[s]=getfa(tmp.fi),in[tmp.fi]=1,clear(),void();
			}
			else {
				e[tmp.se].push_back(tmp.fi);
				if (!rev[tmp.se]) rev[tmp.se]=1,h.push_back(tmp.se);
			}
		}
		for (auto tmp:e[col[x]]) if (!vis[tmp]) {
			q[++tail]=tmp;
			vis[tmp]=1;
			keys[col[tmp]]=1;
			if (getfa(tmp)!=s) return fa[s]=getfa(tmp),in[tmp]=1,clear(),void();
		}
		e[col[x]].clear();
	}
	fl[s]=1;
	int res=tail;
	if (res<ans) {
		ans=res;cnt=0;
		for (i=1;i<=tail;i++) Ans[++cnt]=q[i];
	}
	else if (ans==res) {
		for (i=1;i<=tail;i++) Ans[++cnt]=q[i];
	}
	clear();
}
// int[] find_reachable(int[] r, int[] u, int[] v, int[] c) {
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int i,x,y,z;
	n=r.size(),m=u.size();
	for (i=0;i<m;i++) {
		x=u[i],y=v[i],z=c[i];
		x++,y++;z++;
		to[x].push_back(mk(y,z));
		to[y].push_back(mk(x,z));
	}
	for (i=1;i<=n;i++) col[i]=r[i-1]+1,fa[i]=i;//,gdb(i,col[i]);
	ans=1e9;int times=0;
	while (1) {
		++times;assert(times<=30);
		int flag=0;
		fill(in,in+n+1,0);
		for (i=1;i<=n;i++) 
			if (getfa(i)==i&&fl[i]==0&&!in[i]) bfs(i),flag=1;
		if (!flag) break; 
	}
	fill(fl,fl+n+1,0);
	for (i=1;i<=cnt;i++) fl[Ans[i]]=1;
	vector<int> O;
	for (i=1;i<=n;i++) if (fl[i]) O.push_back(1);else O.push_back(0);
	return O;
}
void init(void) {
	int i,x,y,z,n,m;
	vector<int>r,u,v,c;
	read(n);read(m);
	for (i=1;i<=n;i++) read(x),r.push_back(x);
	for (i=1;i<=m;i++) {
		read(x);read(y);read(z);
		u.push_back(x);v.push_back(y);c.push_back(z);
	}
	vector<int>a=find_reachable(r,u,v,c);
	for (auto tmp:a) printf("%d ",tmp);put();
}