2023 杭电多校4 1011#
Circuit
题目大意
给定一张有向图，求出图上的最小环的长度以及个数。
题解
在做这题之前先来回忆一下 $Floyd$ 的做法——在最开始的做法中首先定义了一个数组 f[k][x][y] ，表示在子图 $V_k’ = \lbrace 1,2,3,…,k\rbrace$ 上 $x, y$ 间的最短路。
计数不重复的关键在于 $k$ 上，在子图 $V_k’$ 上，只记录点 $k$ 此时所在的环，从前往后枚举 $k$ 可以保证计数做到不重不漏，因为点 $k$ 在子图 $V_1’,V_2’,…,V_{k-1}’$ 上不存在，因此先前的计数与与之后的计数一定不重复，同时子图 $V_k’$ 对于子图 $V_{k - 1}’$ 多了点 $k$，找到点 $k$ 在 $V_k’$ 上环就是新增的环个数，保证不漏。
找最小环只需要求出 $i, j$ 的最短路 $d_{i,j}$ 以及一条边 $j \rightarrow i, w$ ，那么这个环的长度就是 $d_{i, j} + w$。
比赛的时候发现只知道 $Floyd$ 怎么用，不知道实现的原理，故未通过。
参考代码：
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
| void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> gra(n, vector<int> (n));
vector<vector<ll>> dis(n, vector<ll> (n, INF));
vector<vector<ll>> cnt(n, vector<ll>(n));
for(int i = 0; i < n; i ++) {
dis[i][i] = 0;
}
for(int i = 0; i < m; i ++) {
int a, b, w;
cin >> a >> b >> w;
a --, b --;
dis[a][b] = w;
gra[a][b] = w;
cnt[a][b] = 1;
}
ll mindis = INF, counter = 0;
for(int k = 0; k < n; k ++) {
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
if(dis[i][j] > dis[i][k] + dis[k][j]) {
cnt[i][j] = cnt[i][k] * cnt[k][j];
dis[i][j] = dis[i][k] + dis[k][j];
} else if(dis[i][j] == dis[i][k] + dis[k][j]) {
cnt[i][j] += cnt[i][k] * cnt[k][j];
}
cnt[i][j] %= mod;
}
}
for(int i = 0; i < k; i ++) {
if(gra[k][i]) {
if(mindis > dis[i][k] + gra[k][i]) {
mindis = dis[i][k] + gra[k][i];
counter = cnt[i][k];
} else if(mindis == dis[i][k] + gra[k][i]) {
counter += cnt[i][k];
}
counter %= mod;
}
}
}
if(mindis == INF) {
mindis = counter = -1;
}
cout << mindis << " " << counter << '\n';
}
|
洛谷 5304#
旅行者
题目大意
给定 $n$ 个点 $m$ 条边的有向图，每条边都有对应的权值，这 $n$ 个点中有 $k$ 个点是我们感兴趣的，求 $k$ 个点中每两个点最短路的最小值。
题解
此题相当于建立一个源点，源点向这 $k$ 个点连一条权为 $0$ 的边，同时建立一个汇点，这 $k$ 个点向汇点连一条权为 $0$ 的边。
，当然，需要将这 $k$ 个点拆成两份，一份作为起点，一份作为终点。在形式上等同于 $Dij$ 最开始将所有 $k$ 个点的起点放入堆中，最后求最短路的时候枚举每个点的终点。但如果只是这样，存在一个非常严重的问题，我们最后得到的结果可能不是每两个点的最短路的最小值，而可能是一个环。如果想用上述方式通过该题，可能需要带着 $set$ 跑 $Dij$。这里介绍一下两种简单的实现方面。
- 假设这个最短路径存在，那么一定存在一条边有别与其他所有等距离的环，可以考虑跑两次 $Dij$，一次跑正向边，一次跑反向边，可以考虑枚举每条边 $(u \rightarrow v, w)$，同时 $check$ 下 $u$ 扩展过来的点和 $v$ 扩展过来的点是否是同一个，那么 $res = min\lbrace dis_1(u) + dis_2(v) + w \rbrace$。可以保证一定能够找到一个非环的最短路径。
参考代码：
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
| const ll INF = 1e18;
void solve() {
int n, m, k;
cin >> n >> m >> k;
n ++;
struct Edge {
int from, to, dis;
};
vector<Edge> es;
vector<vector<Edge>> g(n * 2), revg(n * 2);
vector<ll> d(n * 2, INF), revd(n * 2, INF);
vector<int> org(n * 2, -1), revorg(n * 2, -1);
for(int i = 0; i < m; i ++) {
int a, b, c;
cin >> a >> b >> c;
es.push_back({a, b, c});
g[a].push_back({a, b + n, c});
g[a + n].push_back({a + n, b + n, c});
revg[b].push_back({b, a + n, c});
revg[b + n].push_back({b + n, a + n, c});
}
vector<int> a(k);
for(int& i : a) {
cin >> i;
}
auto Dij = [&](const vector<vector<Edge>>& gra, vector<ll>& dis, vector<int>& orgin) {
vector<bool> vis(2 * n);
priority_queue<PII, vector<PII>, greater<PII>> pq;
for(const int& i : a) {
dis[i] = 0;
orgin[i] = i;
pq.push({dis[i], i});
}
while(pq.size()) {
int u = pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto &[z, v, d] : gra[u]) {
if(dis[v] > dis[u] + d) {
dis[v] = dis[u] + d;
orgin[v] = orgin[u];
pq.push({dis[v], v});
}
}
}
};
Dij(g, d, org);
Dij(revg, revd, revorg);
ll res = INF;
for(const auto &[u, v, dis] : es) {
if(org[u + n] != revorg[v + n]) {
res = min(res, d[u + n] + revd[v + n] + dis);
}
if(org[u] != revorg[v + n]) {
res = min(res, d[u] + revd[v + n] + dis);
}
if(org[u + n] != revorg[v]) {
res = min(res, d[u + n] + revd[v] + dis);
}
if(org[u] != revorg[v]) {
res = min(res, d[u] + revd[v] + dis);
}
}
cout << res << '\n';
}
|
- 考虑将 $k$ 个点成两组分别放在起点和终点，可以证明最多只需要进行 $log\ k$ 次 $Dij$ 就能够找到最短路的最小值。$x$ 从 $1$ 枚举到 $log\ k$，若 $x$ 第 $i$ 位上为 $1$ ，则将第 $p_i$ 个点放在起点，反之放在终点。保证，任意两个点至少分别被放到起点和终点一次。
类似汉明码的做法
CF1818 D#
Fish Graph
题目大意
要求在给定的图上找一个子图，满足“鱼图”的性质，“鱼图”的定义是仅存在一个简单环，并且存在一个环上的特殊点满足连接两条额外的边，另一端点不在环上。
题解
发现这个特殊点有很明显的特征，度大于等于$4$且在一个环上。判断一个点是否在环上可以用tarjan的做法来实现，这里给出一份代码实现：
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
| vector<int> dfn(n), low(n);
vector<bool> vis(n), in_cir(n);
int tim = 0;
stack<int> stk;
auto tarjan = [&](auto self, int u, int f) -> void {
dfn[u] = low[u] = ++ tim;
vis[u] = 1;
stk.push(u);
for(auto &v : e[u]) if(v != f) {
if(!dfn[v]) {
self(self, v, u);
low[u] = min(low[u], low[v]);
} else {
if(vis[v]) {
low[u] = min(low[u], low[v]);
}
}
}
if(low[u] == dfn[u]) {
int now;
vector<int> cand;
do {
now = stk.top();
cand.push_back(now);
stk.pop();
vis[now] = 0;
} while(now != u);
if(cand.size() >= 2) {
for(int i : cand) {
in_cir[i] = true;
}
}
}
};
for(int i = 0; i < n; i ++) {
if(!dfn[i]) {
tarjan(tarjan, i, i);
}
}
|
当我们找一个特殊点后，发现还有一个比较棘手的问题，我们通过dfs找到的环可能不是最小环，比如说
找到类似红色边所围成的环。这会影响我们最终能否找到答案，因此这个问题是必须要解决的，赛场写的时候正是因为处理不了这一点而没做出来。
但是本题实际上并不需要找到最小环。可以通过这个特殊点找到两条不在环上的边，如果边的另一端不在环上，那么不需要进行任何操作，如何这个点在环上，那么实际上可以通过这条边来达到缩小环的目的，最多只需要通过缩小两次环就可以达到最终所需要的结果。比如说可以将上图转化成下面这种样子
时间复杂度$O(n + m)$
参考代码：204409376
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
| void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> e(n);
for(int i = 0; i < m; i ++) {
int a, b;
cin >> a >> b;
a --, b --;
e[a].push_back(b);
e[b].push_back(a);
}
vector<int> dfn(n), low(n);
vector<bool> vis(n), in_cir(n);
int tim = 0;
stack<int> stk;
auto tarjan = [&](auto self, int u, int f) -> void {
dfn[u] = low[u] = ++ tim;
vis[u] = 1;
stk.push(u);
for(auto &v : e[u]) if(v != f) {
if(!dfn[v]) { // 父子边
self(self, v, u);
low[u] = min(low[u], low[v]); // 更新low
} else {
if(vis[v]) {
low[u] = min(low[u], low[v]);
}
}
}
if(low[u] == dfn[u]) {
int now;
vector<int> cand;
do {
now = stk.top();
cand.push_back(now);
stk.pop();
vis[now] = 0;
} while(now != u);
if(cand.size() >= 2) {
for(int i : cand) {
in_cir[i] = true;
}
}
}
};
for(int i = 0; i < n; i ++) {
if(!dfn[i]) {
tarjan(tarjan, i, i);
}
}
for(int i = 0; i < n; i ++) {
if(e[i].size() >= 4 && in_cir[i]) {
vector<int> path;
vector<int> loop;
vector<bool> vis(n);
auto dfs = [&](auto self, int u, int fa) -> void {
vis[u] = true;
path.push_back(u);
for(int v : e[u]) if(v != fa) {
if(v == i) {
loop = path;
return;
}
if(!vis[v]) {
self(self, v, u);
}
if(loop.size()) {
return;
}
}
path.pop_back();
vis[u] = false;
};
dfs(dfs, i, -1);
cout << "YES\n";
vector<int> ex;
for(int v : e[i]) {
if(v != loop[1] && v != loop.back()) {
ex.push_back(v);
}
if(ex.size() == 2) {
break;
}
}
set<int> s;
for(int v : loop) {
s.insert(v);
}
int temp ;
if(s.count(ex[0])) {
temp = loop.back();
while(loop.back() != ex[0]) {
s.erase(s.find(loop.back()));
loop.pop_back();
}
ex[0] = temp;
}
if(s.count(ex[1])) {
temp = loop.back();
while(loop.back() != ex[1]) {
s.erase(s.find(loop.back()));
loop.pop_back();
}
ex[1] = temp;
}
vector<PII> res;
for(int i = 0; i < loop.size(); i ++) {
res.push_back({loop[i] + 1, loop[(i + 1) % loop.size()] + 1});
}
res.push_back({loop[0] + 1, ex[0] + 1});
res.push_back({loop[0] + 1, ex[1] + 1});
cout << res.size() << '\n';
for(auto &[a, b] : res) {
cout << a << " " << b << '\n';
}
return;
}
}
cout << "NO\n";
}
|
CF1822 F#
Gardening Friends
题目大意
给定一棵有根树，根为$1$，可以通过花费$c$的价值使根改变成当前根的邻居，以$i$为根的树的价值是$树的深度 * k$，求可能的最大价值。
题解
发现当且仅有根移动到叶子节点时才有意义。最开始的想法是以为叶子结点的个数为$log\ n$（误当成满二叉树树算了），然后以每一个叶子结点为根算出树的深度计算答案，发现 TLE7，遇到菊花图就铁寄了。
于是开始想$O(1)$转移的方法。考虑到答案实际上可以由两条链构成的，那么可以枚举两条链的交点（两个叶子节点的最近祖先）。那么对于任何一个交点，其实只需要考虑三条链：子树的最长链，子树的次长链，通过根到达另一棵子树的最长链，其中第三条链是不需要考虑的，因为如果根结点有多于两个儿子的时候，我们通过根的最长链和次长链（不是同一个儿子的）就将得到了一个下限值，通过第三条链得到的所有值都小于等于这个下限。
那么对于任何一个交点可以得到$O(1)$的转移方法：
$$
res = max(res, (max1[i] + max2[i] - dep[i] * 2) * k - (max2[i] - 1) * c)
$$
其中$max1[i]$表示$i$结点的最长链的最远端深度，$max2[i]$则表示次长链的最远端深度，$dep[i]$表示$i$结点的深度。
参考代码：204391563
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
| void solve() {
int n, k, c;
cin >> n >> k >> c;
vector<vector<int>> g(n);
for(int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v;
u --, v --;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> dep(n);
vector<int> max1(n, -1), max2(n, -1);
auto dfs = [&](auto self, int u, int fa) -> void {
dep[u] = dep[fa] + 1;
for(int v : g[u]) if(v != fa) {
self(self, v, u);
int m1 = max1[v];
if(m1 == -1) m1 = dep[v];
if(max1[u] == -1) {
max1[u] = m1;
} else if(max2[u] == -1 || max2[u] < m1) {
max2[u] = m1;
if(max2[u] > max1[u]) {
swap(max2[u], max1[u]);
}
}
}
};
dfs(dfs, 0, 0);
i64 res = 1ll * (*max_element(dep.begin(), dep.end()) - 1) * k;
for(int i = 0; i < n; i ++) {
if(max2[i] != -1 && max1[i] != -1)
res = max(res, 1ll * (max1[i] + max2[i] - dep[i] * 2) * k - 1ll * (max2[i] - 1) * c);
}
cout << res << '\n';
}
|
2021 ICPC上海 H#
Life is a Game
题目大意:
给定一张$n$个点$m$条边的无向连通图, 每个点拥有点权$a$, 每条边拥有边权$w$. 有$q$次询问, 每次询问给定初始点$x$和初始能力值$k$, 从$x$点出发, 可以通过小于等于当前能力值的边到达另一个点, 每次到达一个未经过的点便获得这个点的点权, 求最大的能力值.
题解
对于任意一张图, 所走过的边一定属于该图的最小生成树, 这一点用Kruskal很容易证明, 对于一条$u, v$的边, 如果点$u$和点$v$已经连通, 这条边的边权一定大于等于$u, v$路径上的所有边的边权.
那么这题的一个朴素想法便是构建该图的最小生成树, 对于每次询问, 从$x$出发, 跑一个优先队列维护的bfs即可, 然而时限显然不够.
对于这类多次询问的问题的优化, 有两种基本的思路: 其一是离线查询；其二是对数据进行预处理（一般是建立数据结构）, 从而降低每次查询的复杂度. 于是对于最小生成树的预处理的 Kruskal 重构树呼之欲出. 我们让重构树的每个点维护其子树的能力增加量和所需的能力值, 分别记作$add$和$limit$, 从点$x$开始, 一直向上搜索它的父节点, 直到无法向上搜素或者搜索到根节点为止. 但是重构树的高度最坏为$n$, 这意味着每次查询的最坏复杂度仍为$O(n)$!
我们需要能够更快得找到最大的限制, 考虑一条树链, 从叶子到根路径上的限制只会增大, 并且对每个结点而言, 计算出结点本身的限制是可以$O(1)$做到的, 那么如果仅有一条树链又是区间求$max$, 那么很容易就想到 ST 表倍增来实现(既然ST表能做, 那么树剖线段树应该也可以! 但是可能会多个 log ). 尝试写一个长度为$2$的转移: $bz[i][1] = max(bz[i][0], bz[fa[i][0]][0])$, 似乎不难理解并且可行, 由此得出倍增的运算
$$
bz[i][j] = max(bz[i][j - 1], bz[fa[i][j - 1]][j - 1])
$$
那么至此此题的最终复杂度$O(qlog\ n)$.
参考代码：205493766
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
| struct EDGE {
int u, v, w;
bool operator< (const EDGE &a) const {
return w < a.w;
};
};
struct DSU {
int N;
vector<int> p;
DSU(int n) {
N = n;
p.resize(n);
for(int i = 0; i < n; i ++) {
p[i] = i;
}
}
int root(int x) {
return p[x] == x ? x : p[x] = root(p[x]);
}
bool merge(int x, int y) {
int X = root(x), Y = root(y);
if(X == Y) return 1;
p[X] = Y;
return 0;
}
};
struct Node {
int f = -1, w = 0;
ll add = 0;
};
Node nd[MAXN << 1];
vector<EDGE> e;
ll bz[MAXN << 1][17];
int fa[MAXN << 1][17];
int n, m, q;
void solve () {
cin >> n >> m >> q;
e.resize(m);
vector<int> a(n);
for(int i = 0; i < n; i ++) {
cin >> a[i];
nd[i].add = a[i];
}
for(auto &[u, v, w] : e) {
cin >> u >> v >> w;
u --, v --;
}
sort(e.begin(), e.end());
DSU dsu(2 * n + 10);
for(auto &[u, v, w] : e) {
int U = dsu.root(u), V = dsu.root(v);
if(U != V) {
dsu.merge(U, n), dsu.merge(V, n);
nd[U].f = nd[V].f = n;
nd[n].add = nd[U].add + nd[V].add;
nd[n].w = w;
n ++;
}
}
for(int i = 0; i < n; i ++) {
fa[i][0] = nd[i].f;
bz[i][0] = nd[nd[i].f].w - nd[i].add;
}
for(int i = 1; i < 17; i ++) {
for(int j = 0; j < n; j ++) {
if(fa[j][i - 1] == - 1) {
fa[j][i] = -1;
continue;
}
fa[j][i] = fa[fa[j][i - 1]][i - 1];
bz[j][i] = max(bz[j][i - 1], bz[fa[j][i - 1]][i - 1]);
}
}
while(q --) {
int x, k;
cin >> x >> k;
x --;
for(int i = 16; i >= 0; i --) {
if(fa[x][i] != -1) {
if(bz[x][i] <= k) {
x = fa[x][i];
}
}
}
ll res = k + nd[x].add;
cout << res << '\n';
}
}
|
2019 ICPC银川 H#
Delivery Route
题目大意
给定一张图，求所有点对于源点$s$的最短路，图中存在$x$条双向边，$y$条单向边，保证双向边的权一定为正整数，单向边的权可能为负，且若$u\rightarrow v$ 存在一条单向边，那么$v$一定无法到达$u$。
题解
因为存在负权边，所以不能直接使用 Dijkstra，且数据大小不允许用 Bellman-Ford（SPFA 已死）。此时注意到第二类边仅会出现在联通分量之间，且联通分量之间是拓扑有序的，因此可以在联通分量间跑拓扑 dp，在联通分量内部跑 Dij。一般我们在跑 Dij 的时候首先往往确定源点的距离为$0$，其他点的距离为$inf$，但此时除了源点所在的联通分量，其他的联通分量似乎找不到一个合适的源点，并且有一些点的值已经确定了一个初值而不是$inf$，因此，可以假设这些已经有初值的点和源点存在一条边，然后略去第一步的过程，将这些点都加入到优先队列之后再跑 Dij。这算考 Dij 的一个变式。
参考代码：205419690
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, mod = 998244353, MAXN = 1e5 + 10;
struct DSU {
int n;
vector<int> pr;
DSU(int n) : n(n) {
pr.resize(n);
for(int i = 0; i < n; i ++) {
pr[i] = i;
}
}
int root(int x) {
return pr[x] == x ? x : pr[x] = root(pr[x]);
}
bool merge(int x, int y) {
int X = root(x), Y = root(y);
if(X == Y) return false;
pr[Y] = X;
return true;
}
};
struct Edge {
int from, to, w;
};
void solve() {
int n, x, y, s;
cin >> n >> x >> y >> s;
s --;
vector<vector<Edge>> e(n);
vector<i64> dis(n, 1e17);
DSU dsu(n);
vector<vector<int>> bel(n);
auto Dij = [&](int s) {
vector<bool> vis(n);
priority_queue<PII, vector<PII>, greater<PII>> q;
for(int u : bel[s]) {
if(dis[u] < 1e9) {
q.push({dis[u], u});
}
}
while(q.size()) {
int d = q.top().first;
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto &[fr, to, w] : e[u]) {
if(dis[to] > dis[u] + w) {
dis[to] = dis[u] + w;
q.push({dis[to], to});
}
}
}
};
for(int i = 0; i < x; i ++) {
int u, v, w;
cin >> u >> v >> w;
u --, v --;
e[u].push_back({u, v, w});
e[v].push_back({v, u, w});
dsu.merge(u, v);
}
for(int i = 0; i < n; i ++) {
bel[dsu.root(i)].push_back(i);
}
vector<vector<Edge>> e2(n);
vector<int> deg(n);
for(int i = 0; i < y; i ++) {
int u, v, w;
cin >> u >> v >> w;
u --, v --;
e2[u].push_back({u, v, w});
deg[dsu.root(v)] ++;
}
queue<int> q;
for(int i = 0; i < n; i ++) {
if(deg[i] == 0 && dsu.root(i) == i) {
q.push(i);
}
}
dis[s] = 0;
while(q.size()) {
int com = q.front();
q.pop();
Dij(com);
for(int nd : bel[com]) {
for(auto &[fr, to, w] : e2[nd]) {
if(dis[to] > dis[fr] + w) {
dis[to] = dis[fr] + w;
// Dij(to);
}
if(! --deg[dsu.root(to)]) {
q.push(dsu.root(to));
}
}
}
}
for(int i = 0; i < n; i ++) {
if(dis[i] > 1e15) {
cout << "NO PATH\n";
} else {
cout << dis[i] << '\n';
}
}
}
signed main () {
ios::sync_with_stdio(0), cin.tie(0);
solve();
}
|
2022 杭电多校 B#
Link with Running
2022 ICPC南京 J#
Perfect Matching
题目大意
给定一张图，存在$n$个点，每个点都有权值$a_i$，如果$|i - j| = |a_i - a_j|$，则$i$和$j$之间存在一条边，构造出图的一个完美匹配，若不能输出No。
题解
由$|i - j| = |a_i - a_j|$可知，连边有两种情况：
$$
\begin{cases}
a_i + i = a_j + j \\
a_i - i = a_j - j
\end{cases}
$$
显然可以建立一张二分图，将第一种情况视为左侧的点，第二种情况的点视为右侧的点，连边的边权是$i$，即原图中的点的编号。接下来考虑如从二分图中构造出答案，将图划分成长度为$2$的不重合链（点可以相同），如果一个联通分量的边数为偶数，那么一定可以构造出来，首先考虑图为树的情况，我们每次考虑链的中间的点，首先考虑$i$节点未被用过的与儿子节点的边，如果个数为奇数，则要加上自己与父节点的边，而在图上只要找到一个$dfn$树，额外考虑返祖边，视为$i$的未被用过的儿子。
可以先解决一下这个子问题，参考这题CF858 F Wizard’s Tour。
这题比较直接，给定一张图，问最多能构造出长度为$2$的不相交链。
参考代码：
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;
void solve() {
int n, m;
cin >> n >> m;
struct Edge {
int form, to;
};
vector<vector<Edge>> G(n);
for(int i = 0; i < m; i ++) {
int a, b;
cin >> a >> b;
a --, b --;
G[a].push_back({a, b});
G[b].push_back({b, a});
}
vector<bool> vis(n);
struct nd {
int a, b, c;
};
vector<nd> res;
vector<int> dep(n);
auto dfs = [&](auto self, int u, int fa, int d) -> bool {
vis[u] = true;
dep[u] = d;
vector<int> cand;
for(auto &[from, to] : G[u]) if(to != fa) {
if(dep[to]) {
if(dep[to] < dep[u]) {
cand.push_back(to);
continue;
}
} else {
if(self(self, to, u, d + 1)) {
cand.push_back(to);
}
}
}
if(u != fa){
cand.push_back(fa);
}
for(int i = 0; i + 1 < cand.size(); i += 2) {
res.push_back({cand[i], u, cand[i + 1]});
}
if(cand.size() & 1) return true;
else return false;
};
for(int i = 0; i < n; i ++) {
if(vis[i]) continue;
dfs(dfs, i, i, 1);
}
cout << res.size() << '\n';
for(auto [a, b, c] : res) {
cout << a + 1 << ' ' << b + 1 << ' ' << c + 1 << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int _ = 1;
while(_ --) {
solve();
}
}
|
这题的代码比上面难点在于建图以及得到反向边的边权，下面的dfs多向下传了顺序的边权解决这个问题，但是下面的代码未进行离散化处理，比标程多了一个$log$。
参考代码： 206725399
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef pair<i64, int> PII;
const int INF = 1e9 + 7, mod = 998244353, MAXN = 1e5 + 10;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i ++) {
cin >> a[i];
}
vector<PII> res;
map<i64, vector<PII>> G;
map<i64, bool> vis;
map<i64, int> dep;
for(int i = 0; i < n; i ++) {
G[a[i] - i - 1].push_back({2ll * INF + a[i] + i + 1, i});
G[a[i] + i + 1 + 2ll * INF].push_back({a[i] - i - 1, i});
}
auto dfs = [&](auto self, i64 u, i64 fa, int d, int rev) -> int {
vis[u] = true;
dep[u] = d;
vector<i64> cand;
for(auto &[to, id] : G[u]) if(to != fa) {
if(dep[to]) {
if(dep[to] < dep[u]) {
cand.push_back(id);
}
} else {
if(self(self, to, u, d + 1, id) >= 0) {
cand.push_back(id);
}
}
}
if(fa != u) {
cand.push_back(rev);
}
for(int i = 0; i + 1 < cand.size(); i += 2) {
res.push_back({cand[i], cand[i + 1]});
}
if(cand.size() % 2 == 0) {
return -2;
} else {
return rev;
}
};
for(auto &[id, vec] : G) {
if(vis[id]) continue;
if(dfs(dfs, id, id, 1, -1) != -2) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
for(auto &[x, y] : res) {
cout << x + 1 << " " << y + 1 << '\n';
}
}
signed main () {
ios::sync_with_stdio(0), cin.tie(0);
int _ = 1;
cin >> _;
while(_--) {
solve();
}
}
|