CF757F Team Rocket Rises Again

为了做这个题学了一下支配树大概是个什么玩意。一般图支配树被鸽了,只写一下 DAG 上支配树的做法。

考虑一个单源有向图,上的一个点 $u$ 如果存在一个点 $v$ 满足删除 $v$ 后 $u$ 无法从源点到达,那么我们称 $v$ 支配点 $u$ 。

显然,同一个点的支配点很多,设这些点是 $v_1,v_2, \dots ,v_k$ ,同时显然源点也是一个支配点。

  • 如果 $a$ 支配 $b$ ,$b$ 支配 $c$ ,那么有 $a$ 支配 $c$ 。证明显然。
  • 如果 $a$ 支配 $c$ ,$b$ 也支配 $c$ ,那么 $a,b$ 间一定存在支配关系。如果不存在,那么显然从原点通过 $a,b$ 均可到达 $c$ ,因此这两个点就都不支配 $c$ 了。

所以 $v_1, \dots ,v_k$ 这个支配点集合满足一个全序关系,因此一定可以找到一个“最小”的支配点,使得其他支配点都支配这个点,我们称之为 $\text{Idom}(x)$ 。

于是支配树的定义就是从 $\text{Idom}(x)$ 向 $x$ 连一条边出去,得到的一个树。

在这道题中,建立了最短路图(是个 DAG )后就成了一个删除一个点,最多可以让多少点不可达的问题,如果建立了支配树,显然答案就是除原树外最大的子树大小。

下面说一下 DAG 怎么建立支配树。我们按照拓扑序从小到大考虑。对于每一个位置,它的父亲就是所有它的前驱在树中位置的 LCA 。因此可以非常方便地建出支配树。

复杂度 $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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 400006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , s;
int A[MAXN];

vector<pii> G[MAXN];

ll dis[MAXN];
int vis[MAXN];
void dijk( ) {
memset( dis , 0x3f , sizeof dis );
dis[s] = 0;
priority_queue<pair<ll,int>> Q;
Q.push( mp( 0ll , s ) );
while( !Q.empty() ) {
int u = Q.top().se; Q.pop();
if( vis[u] ) continue;
vis[u] = 1;
for( auto t : G[u] ) if( dis[u] + t.se < dis[t.fi] ) {
int v = t.fi;
dis[v] = dis[u] + t.se;
Q.push( mp( -dis[v] , v ) );
}
}
}

vi g[MAXN] , rg[MAXN] , Gt[MAXN];
int deg[MAXN];

int J[MAXN][20] , dep[MAXN];
int lca( int u , int v ) {
if( dep[u] < dep[v] ) swap( u , v );
if( dep[u] != dep[v] )
per( k , 17 , 0 ) if( dep[J[u][k]] >= dep[v] ) u = J[u][k];
if( u == v ) return u;
per( k , 17 , 0 ) if( J[u][k] != J[v][k] ) u = J[u][k] , v = J[v][k];
return J[u][0];
}

int sz[MAXN];
int as;
void dfs( int u ) {
sz[u] = 1;
for( int v : Gt[u] ) dfs( v ) , sz[u] += sz[v];
if( u != s ) as = max( as , sz[u] );
}

void solve() {
cin >> n >> m >> s;
rep( i , 1 , m ) {
int u , v , w;
scanf("%d%d%d",&u,&v,&w);
G[u].eb( mp( v , w ) ) , G[v].eb( mp( u , w ) );
}
dijk( );
rep( u , 1 , n ) for( auto t : G[u] ) if( dis[t.fi] == dis[u] + t.se )
g[u].pb( t.fi ) , rg[t.fi].pb( u ) , ++ deg[t.fi];
queue<int> Q;
Q.push( s );
while( !Q.empty() ) {
int u = Q.front(); Q.pop();
for( int v : g[u] ) {
-- deg[v];
if( !deg[v] ) Q.push( v );
}
int cv = 0;
for( int v : rg[u] ) {
if( !cv ) cv = v;
else cv = lca( cv , v );
}
dep[u] = dep[cv] + 1;
if( !cv ) continue;
J[u][0] = cv;
Gt[cv].pb( u );
rep( k , 1 , 17 ) if( J[J[u][k - 1]][k - 1] )
J[u][k] = J[J[u][k - 1]][k - 1]; else break;
}
dfs( s );
cout << as << endl;
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2021/04/19/cf757f-team-rocket-rises-again/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog