树链剖分专题
Posted Updated Notes26 minutes read (About 3949 words)

树链剖分专题

显然的板子题。

那么我们只需要干这样一件事情，就是按照重儿子的顺序来进行 DFS，那么这样我们就可以通过 DFS 序这样一个东西来进行子树的查询和更改，同时也可以通过跳链顶，类似 LCA 的操作，来进行路径的修改和查询。这都非常容易实现。

所以代码会长下面这样。

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 int long long
using namespace std;

const int N = 1e5 + 10;

int n, m, root, Mod, cnt, idx;
int w[N], wl[N], val[N<<2], head[N<<1];
int dep[N], id[N], fa[N], son[N];
int lazy[N<<2], tp[N], siz[N];

struct Edge {
  int to, nxt;
} e[N<<1];

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

void pushup(int rt) {
  val[rt] = (val[ls] + val[rs]) % Mod;
  return ;
}

void build(int rt, int l, int r) {
  if (l==r) { val[rt] = wl[l]; return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid);
  build(rs, mid+1, r);
  pushup(rt); return ;
}

void pushdown(int rt, int l, int r) {
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
  lazy[ls] %= Mod, lazy[rs] %= Mod;
  val[ls] = (val[ls] + (mid-l+1) * lazy[rt]) % Mod;
  val[rs] = (val[rs] + (r-mid) * lazy[rt]) % Mod;
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int f) {
  if (L<=l && r<=R) {
    val[rt] += (r-l+1) * f, val[rt] %= Mod;
    lazy[rt] += f, lazy[rt] %= Mod;
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, f);
  if (R>mid) upd(rs, mid+1, r, L, R, f);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans % Mod;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  siz[cur] = 1, fa[cur] = f;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to]>heavyson)
      heavyson = siz[to], son[cur] = to;
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++idx, wl[idx] = w[cur];
  tp[cur] = Tp; if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==son[cur] || to==fa[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

void up(int l, int r, int f) {
  f %= Mod;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], f);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], f);
  return ;
}

int qu(int l, int r) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans = (ans + query(1, 1, n, id[tp[l]], id[l])) % Mod;
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans = (ans + query(1, 1, n, id[l], id[r])) % Mod;
  return ans;
}

void upsub(int x, int f) { upd(1, 1, n, id[x], id[x]+siz[x]-1, f); }
int qusub(int x) { return query(1, 1, n, id[x], id[x]+siz[x]-1); }

signed main() {
  read(n), read(m);
  read(root), read(Mod);
  for (int i=1; i<=n; ++i) read(w[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs1(root, root);
  dfs2(root, 0); build(1, 1, n);
  while (m--) {
    int opt, x, y, z;
    read(opt);
    if (opt==1) {
      read(x), read(y), read(z);
      up(x, y, z);
    } else if (opt==2) {
      read(x), read(y);
      printf("%lld\n", qu(x, y) % Mod);
    } else if (opt==3) {
      read(x), read(z);
      upsub(x, z);
    } else { read(x); printf("%lld\n", qusub(x) % Mod); }
  }
  return 0;
}

更简单了，甚至不需要 lazytag。

代码如下。

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 <stdio.h>
#include <iostream>
#define isdigit(ch) (ch>47&&ch<58)

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch ^ '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

void out(int ret) {
  if (ret<0) { ret = -ret, putchar('-'); }
  if (ret>9) out(ret/10);
  putchar(ret%10 ^ 48); return ;
}

const int N = 3e4 + 10;
int n, Q, cnt, dfn;
int w[N], v[N], head[N];

int val[N<<2], siz[N], Maxi[N<<2];
int id[N], fa[N], tp[N], son[N], dep[N];
char str[10];

int max(int x, int y) { return x>y? x:y; }
void swap(int &x, int &y) { x ^= y ^= x ^= y; }

struct Edge {
  int to, nxt;
} e[N<<1];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt;
  return ;
}

void pushup(int rt) {
  val[rt] = val[ls] + val[rs];
  Maxi[rt] = max(Maxi[ls], Maxi[rs]);
  return ;
}

void build(int rt, int l, int r) {
  if (l == r) { val[rt] = Maxi[rt] = v[l]; return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid);
  build(rs, mid+1, r);
  pushup(rt); return ;
}

void upd(int rt, int l, int r, int pos, int f) {
  if (l == r) { val[rt] = Maxi[rt] = f; return ; }
  int mid = (l+r) >> 1;
  if (pos<=mid) upd(ls, l, mid, pos, f);
  if (pos>mid) upd(rs, mid+1, r, pos, f);
  pushup(rt); return ;
}

int querys(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += querys(ls, l, mid, L, R);
  if (R>mid) ans += querys(rs, mid+1, r, L, R);
  return ans;
}

int querym(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return Maxi[rt];
  int mid = (l+r) >> 1, Max = -1e9;
  if (L<=mid) Max = max(Max, querym(ls, l, mid, L, R));
  if (R>mid) Max = max(Max, querym(rs, mid+1, r, L, R));
  return Max;
}

void dfs1(int cur, int Fa) {
  dep[cur] = dep[Fa] + 1;
  fa[cur] = Fa, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == Fa) continue;
    dfs1(to, cur);
    siz[cur] += siz[to];
    if (siz[to] > heavyson)
      son[cur] = to, heavyson = siz[to];
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++dfn;
  v[dfn] = w[cur], tp[cur] = Tp;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == fa[cur] || to == son[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

int qus(int l, int r) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    int cur = querys(1, 1, n, id[tp[l]], id[l]);
    ans += cur, l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans += querys(1, 1, n, id[l], id[r]);
  return ans;
}

int qum(int l, int r) {
  int ans = -1e9;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    int cur = querym(1, 1, n, id[tp[l]], id[l]);
    ans = max(ans, cur), l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans = max(ans, querym(1, 1, n, id[l], id[r]));
  return ans;
}

int main() {
//   freopen("P2590.in", "r", stdin);
//   freopen("P2590.out", "w", stdout);
  read(n);
  for (int i=1; i<n; ++i) {
    int x, y; read(x), read(y);
    addEdge(x, y), addEdge(y, x);
  }
  for (int i=1; i<=n; ++i) read(w[i]);

  dfs1(1, 1), dfs2(1, 1);
  build(1, 1, n);

  read(Q);
  while (Q--) {
    std::cin >> str+1;
    int l, r; read(l), read(r);
    if (str[1] == 'C') upd(1, 1, n, id[l], r);
    else if (str[2] == 'M') out(qum(l, r)), puts("");
    else if (str[2] == 'S') out(qus(l, r)), puts("");
  }
  return 0;
}

简单 trick。

只需要将依赖关系转化为树上关系就可以了。
然后就是要区分 0 和 unedited，完全不一样。
所以可以直接将 unedited 设置为 -1 然后乱搞即可。

注意是赋值而不是加法。

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
#include <bits/stdc++.h>
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int N = 1e5 + 10;
int n, Q, cnt, idx, head[N];
int val[N<<2], lazy[N<<2];
int id[N], tp[N], siz[N], dep[N];
char opt[20]; int fa[N], son[N];

struct Edge { int to, nxt; } e[N];

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  val[rt] = val[ls] + val[rs];
  return ;
}

void pushdown(int rt, int l, int r) {
  if (lazy[rt]<0) return ;
  int mid = (l+r) >> 1;
  lazy[ls] = lazy[rt], lazy[rs] = lazy[rt];
  val[ls] = lazy[rt] * (mid-l+1);
  val[rs] = lazy[rt] * (r-mid);
  lazy[rt] = -1; return ;
}

void upd(int rt, int l, int r, int L, int R, int f) {
  if (L<=l && r<=R) {
    lazy[rt] = f; val[rt] = f * (r-l+1);
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, f);
  if (R>mid) upd(rs, mid+1, r, L, R, f);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  fa[cur] = f, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++idx; tp[cur] = Tp;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==son[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

void up(int l, int r, int f) {
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], f);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], f);
  return ;
}

int main() {
//   freopen("P2146.in", "r", stdin);
  memset(lazy, -1, sizeof lazy);
  read(n);
  for (int i=2; i<=n; ++i) {
    int v; read(v);
    addEdge(v+1, i);
  }
  dfs1(1, 1), dfs2(1, 1), read(Q);
  while (Q--) {
    cin >> opt+1;
    int v; read(v); ++v;
    int cur = query(1, 1, n, 1, n);
    if (opt[1]=='i') up(1, v, 1);
    else if (opt[1]=='u') upd(1, 1, n, id[v], id[v]+siz[v]-1, 0);
    int to = query(1, 1, n, 1, n);
    printf("%d\n", abs(cur-to));
  }
  return 0;
}

也是个简单题，就是不要被 from 和 to 骗了，双向边肯定要连的。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  }
  ret *= f; return ;
}

const int N = 1e5 + 10;

int n, m, cnt, idx;
int dep[N], son[N], fa[N], siz[N];
int head[N<<1], tp[N], w[N], wl[N], id[N];
struct Edge { int to, nxt; } e[N<<1];

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

int lazy[N<<2], val[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  val[rt] = val[ls] + val[rs];
  return ;
}

void build(int rt, int l, int r) {
  if (l==r) { val[rt] = wl[l]; return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid);
  build(rs, mid+1, r);
  pushup(rt); return ;
}

void pushdown(int rt, int l, int r) {
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
  val[ls] += (mid-l+1) * lazy[rt];
  val[rs] += (r-mid) * lazy[rt];
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int f) {
  if (L<=l && r<=R) { lazy[rt] += f; val[rt] += f * (r-l+1); return ; }
  int mid = (l+r) >> 1; pushdown(rt, l, r);
  if (L<=mid) upd(ls, l, mid, L, R, f);
  if (R>mid) upd(rs, mid+1, r, L, R, f);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  int ans = 0, mid = (l+r) >> 1;
  pushdown(rt, l, r);
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans;
}

void dfs1(int cur, int f) {
  fa[cur] = f, siz[cur] = 1;
  dep[cur] = dep[f] + 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==f) continue;
    dfs1(to, cur); siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++idx, wl[idx] = w[cur];
  tp[cur] = Tp;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa[cur] || to==son[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

int que(int l, int r) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans += query(1, 1, n, id[tp[l]], id[l]);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans += query(1, 1, n, id[l], id[r]);
  return ans;
}

signed main() {
  read(n), read(m);
  for (int i=1; i<=n; ++i) read(w[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs1(1, 1), dfs2(1, 1);
  build(1, 1, n);
  while (m--) {
    int opt, x, a; read(opt), read(x);
    if (opt==1) {
      read(a);
      upd(1, 1, n, id[x], id[x], a);
    } else if (opt==2) {
      read(a);
      upd(1, 1, n, id[x], id[x]+siz[x]-1, a);
    } else printf("%lld\n", que(1, x));
  }
  return 0;
}

毒瘤出题人搞边不搞点。

看到题目首先想到树链剖分。
首先变为重边的操作不难，直接普通树链剖分即可。
查询路径上包含所有重边也很简单，只需要标记为 1 然后统计和。

但是 ex 的在于将点 $x$ 的所有连边变为轻边。

所以应该怎么弄呢？
那么很容易想到树链剖分的染色。

可以这样做：每一次路径变为重边就可以看成是给路径上所有点染一种 新的 颜色。
那么这个时候，看到所有其他连边连向的点都和当前路径上点的颜色不一样。
这个时候就可以默认其变为了轻边。

所以这样就可以得出判断轻边的条件了。
就是一条边，如果它两端颜色相同就为重边。
证明显然。

然后就是关于区间修改的问题了。
因为当前是求区间两端颜色相同边的个数，所以考虑树链剖分，将一段路径拆成若干区间，每一次合并区间都可以加上子区间答案，并保证其正确性，显而易见这样是不会假掉的。
要注意的就是如果子区间中间连接的两点颜色相同答案要加上 $1$。

那路径修改呢？这样还是有很大区别的。
因为两点之间路径可以视作从一个点剖开变成两条路径。
所以考虑两条路径分别维护。

那么我们可以对于每一个跳链顶的过程，记录当前 update 的是以 $u$ 为起点的路径还是以 $v$ 为起点的路径（$u \rightarrow v$ 为路径），每一次看维护两个指针 L 和 R 是否交换即可，最后还要合并答案，这里还是要详细讲一下。

不考虑整条路径两个指针 L，R 的实际位置，只考虑相对位置。
那么有两种情况。

  • L 跳到了但是 R 没有跳到。

显然这个时候 dep[L]<dep[R]。
又因为 L 跳到了，所以上一次更新的是 L 路径，本次就要更新 R 路径了。
所以本轮不用交换 L 和 R，L 路径和 R 路径的 tag 仍然指向 L。
这里就是容易弄混的地方，指向 L 的 tag 在这时要更新 R 路径。

  • R 跳到了但是 L 没有跳到。

显然这个时候 dep[L]>dep[R]。
又因为 R 跳到了，所以上面的 tag 指向 R，本次更新 L 路径。
因为当前这样所以要交换 L 和 R，tag 反转之后指向当前 R，所以相当于更新交换之后的 R 路径，本质还是 L 路径。（我自己都晕了）
反正不偷懒的写法会好理解一些，手动模拟比较好一点。

大概就是分 L 先到和 R 先到的情况吧。
其实手玩一下也是没有问题的，手玩完之后再写暴力更新的代码。

另外一点，我这里默认 L 路径在左边，其 dep[l]>dep[r]。
而 R 路径默认在右边，其 dep[l]<dep[r]。

lc 和 rc 分别是 leftcolor，rightcolor。

注意一开始如果全部没有染色那默认全都为 $0$，那么重边的条数就变成 $n-1$ 了，which is totally wrong。所以一开始就要染奇奇怪怪的颜色。
接着注意边数等于点数减一，在 pushdown 和 update 的时候要注意。

代码如下。

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
159
160
161
162
163
164
165
166
167
168
169
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int T, n, m, cnt, idx, lazy[N<<2];
int head[N<<1], dep[N], siz[N];
int tp[N], son[N], fa[N], id[N];

struct Edge { int to, nxt; } e[N<<1];
struct seg {
  int lc, rc, val;
  seg(int lc, int rc, int val):
    lc(lc), rc(rc), val(val) {}
  seg() {}
} tree[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  tree[rt].lc = tree[ls].lc;
  tree[rt].rc = tree[rs].rc;
  tree[rt].val = tree[ls].val + tree[rs].val;
  if (tree[ls].rc == tree[rs].lc) ++tree[rt].val;
  return ;
}

seg Merge(seg L, seg R) {
  seg cur; cur.lc = L.lc, cur.rc = R.rc;
  cur.val = L.val + R.val;
  if (L.rc == R.lc) ++cur.val;
  return cur;
}

void pushdown(int rt, int l, int r) {
  // lazy[rt] -> stores the color
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] = lazy[rs] = lazy[rt];
  tree[ls] = seg(lazy[rt], lazy[rt], mid-l); // (mid-l+1)-1
  tree[rs] = seg(lazy[rt], lazy[rt], r-mid-1); // (r-mid)-1
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int col) {
  if (L<=l && r<=R) {
    lazy[rt] = col;
    tree[rt] = seg(col, col, r-l); // (r-l+1)-1
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, col);
  if (R>mid) upd(rs, mid+1, r, L, R, col);
  pushup(rt); return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, tag = 0;
  seg ans1, ans2;
  if (L<=mid) ans1 = query(ls, l, mid, L, R), ++tag;
  if (R>mid) ans2 = query(rs, mid+1, r, L, R), tag += 2;
  if (tag == 1) return ans1; else if (tag == 2) return ans2;
  return Merge(ans1, ans2);
}

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  fa[cur] = f, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  } return ;
}

void dfs2(int cur, int Tp) {
  tp[cur] = Tp, id[cur] = ++idx;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == son[cur] || to == fa[cur]) continue;
    dfs2(to, to);
  } return ;
}

void up(int l, int r, int col) {
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], col);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], col);
  return ;
}

const seg NUL = seg(0, 0, 0);
int qu(int l, int r) {
  int belong = 0; seg ans[2];
  ans[0] = seg(0, 0, 0), ans[1] = ans[0];
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) {
      belong = 1 - belong;
      swap(l, r);
    }
    seg cur = query(1, 1, n, id[tp[l]], id[l]);
    if (belong) ans[1] = Merge(cur, ans[1]);
    else ans[0] = seg(ans[0].lc, cur.lc,
    ans[0].val+cur.val+(ans[0].rc==cur.rc));
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) {
    belong = 1 - belong;
    swap(l, r);
  }
  seg cur = query(1, 1, n, id[l], id[r]);
  if (!belong) ans[1] = Merge(cur, ans[1]);
  else ans[0] = seg(ans[0].lc, cur.lc,
  ans[0].val+cur.val+(ans[0].rc==cur.rc));
  return Merge(ans[0], ans[1]).val;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

int main() {
  read(T);
  while (T--) {
    read(n), read(m);
    cnt = idx = 0;
    for (int i=1; i<=n; ++i) {
      siz[i] = dep[i] = son[i] = 0;
      id[i] = tp[i] = fa[i] = head[i] = 0;
      tree[i*4-3] = tree[i*4-2] = tree[i*4-1] = tree[i*4] = NUL;
      lazy[i*4-3] = lazy[i*4-2] = lazy[i*4-1] = lazy[i*4] = 0;
    }
    for (int i=1; i<n; ++i) {
      int u, v; read(u), read(v);
      addEdge(u, v), addEdge(v, u);
    }
    dfs1(1, 1), dfs2(1, 1);
    for (int i=1; i<=n; ++i) upd(1, 1, n, id[i], id[i], -i);
    while (m--) {
      int opt, u, v; read(opt), read(u), read(v);
      if (opt == 1) up(u, v, m);
      else printf("%d\n", qu(u, v));
    }
  }
  return 0;
}

什么时候 NOI 能出一些不重复的题目啊 …（指 NOI2021 D1T1）
这个 trick 和上面一题几乎一致，但是这个时候初始贡献为 $1$。
每一次 update 的区间贡献都为 $1$，判断 ls.rc=rs.lc 那么贡献 $-1$。

代码如下。

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, cnt, idx, lazy[N<<2];
int head[N<<1], dep[N], siz[N];
int tp[N], son[N], fa[N], id[N];
int w[N], wl[N];

struct Edge { int to, nxt; } e[N<<1];
struct seg {
  int lc, rc, val;
  seg(int lc, int rc, int val):
    lc(lc), rc(rc), val(val) {}
  seg() {}
} tree[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  tree[rt].lc = tree[ls].lc;
  tree[rt].rc = tree[rs].rc;
  tree[rt].val = tree[ls].val + tree[rs].val;
  if (tree[ls].rc == tree[rs].lc) --tree[rt].val;
  return ;
}

seg Merge(seg L, seg R) {
  seg cur; cur.lc = L.lc, cur.rc = R.rc;
  cur.val = L.val + R.val;
  if (L.rc == R.lc) --cur.val;
  return cur;
}

void pushdown(int rt, int l, int r) {
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] = lazy[rs] = lazy[rt];
  tree[ls] = seg(lazy[rt], lazy[rt], 1);
  tree[rs] = seg(lazy[rt], lazy[rt], 1);
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int col) {
  if (L<=l && r<=R) {
    lazy[rt] = col;
    tree[rt] = seg(col, col, 1);
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, col);
  if (R>mid) upd(rs, mid+1, r, L, R, col);
  pushup(rt); return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, tag = 0;
  seg ans1, ans2;
  if (L<=mid) ans1 = query(ls, l, mid, L, R), ++tag;
  if (R>mid) ans2 = query(rs, mid+1, r, L, R), tag += 2;
  if (tag == 1) return ans1; if (tag == 2) return ans2;
  return Merge(ans1, ans2);
}

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  fa[cur] = f, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  } return ;
}

void dfs2(int cur, int Tp) {
  tp[cur] = Tp, id[cur] = ++idx, wl[idx] = w[cur];
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == fa[cur] || to == son[cur]) continue;
    dfs2(to, to);
  } return ;
}

void up(int l, int r, int col) {
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], col);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], col);
  return ;
}

const seg NUL = seg(0, 0, 0);
int qu(int l, int r) {
  int belong = 0; seg ans[2];
  ans[0] = ans[1] = NUL;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) {
      belong = 1 - belong;
      swap(l, r);
    }
    seg cur = query(1, 1, n, id[tp[l]], id[l]);
    if (belong) ans[1] = Merge(cur, ans[1]);
    else ans[0] = seg(ans[0].lc, cur.lc,
    ans[0].val+cur.val-(ans[0].rc==cur.rc));
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) {
    belong = 1 - belong;
    swap(l, r);
  }
  seg cur = query(1, 1, n, id[l], id[r]);
  if (!belong) ans[1] = Merge(cur, ans[1]);
  else ans[0] = seg(ans[0].lc, cur.lc,
  ans[0].val+cur.val-(ans[0].rc==cur.rc));
  return Merge(ans[0], ans[1]).val;
}

void build(int rt, int l, int r) {
  if (l==r) {
    tree[rt].val = 1;
    tree[rt].lc = tree[rt].rc = wl[l];
    return ;
  }
  int mid = (l+r) >> 1;
  build(ls, l, mid), build(rs, mid+1, r);
  pushup(rt); return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

int main() {
  read(n), read(m);
  for (int i=1; i<=n; ++i) read(w[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v), addEdge(v, u);
  }
  dfs1(1, 1), dfs2(1, 1);
  build(1, 1, n);
  while (m--) {
    char opt; cin >> opt;
    int u, v, color;
    read(u), read(v);
    if (opt == 'C') read(color), up(u, v, color);
    else printf("%d\n", qu(u, v));
  }
  return 0;
}
网络流 24 题 trick 记录（含代码）
Posted Updated Notes19 minutes read (About 2826 words)

网络流 24 题 trick 记录（含代码）

只要默认前面 $m$ 个都是外国的，然后剩下的都是英国的，接着暴力建图跑 Dinic 即可。
貌似只需要弄一个源点 $0$ 和汇点 $n+1$ 即可。

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
#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int N = 2e4 + 10;
int n, m, cnt = 1;
int head[N], dep[N];
bool vis[N];

struct Edge {
  int to, nxt, val;
} e[N];

void addEdge(int u, int v, int w) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].val = w;
  head[u] = cnt; return ;
}

bool check() {
  for (int i=0; i<=n+1; ++i) dep[i] = 0;
  dep[0] = 2; queue <int> sp; sp.push(0);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (!dep[to] && e[i].val) {
        dep[to] = dep[cur] + 1, sp.push(to);
        if (to==n+1) return true;
      }
    }
  }
  return false;
}

int dfs(int cur, int Max) {
  if (cur==n+1) return Max;
  int increase = Max;
  for (int i=head[cur]; i&&increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].val && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].val));
      e[i].val -= res, e[i^1].val += res;
      if (!res) dep[to] = 0;
      increase -= res;
    }
  }
  return Max-increase;
}

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

int main() {
  read(m), read(n);
  while (1) {
    int u, v; read(u), read(v);
    if (u==-1 && v==-1) break;
    addEdge(u, v, inf);
    addEdge(v, u, 0);
  }
  for (int i=1; i<=m; ++i)
    addEdge(0, i, 1), addEdge(i, 0, 0);
  for (int i=m+1; i<=n; ++i)
    addEdge(i, n+1, 1), addEdge(n+1, i, 0);
  int ans = 0;
  while(check()) ans += dfs(0, inf);
  cout << ans << endl;
  for (int i=2; i<=cnt; i+=2) {
    if (!e[i^1].val) continue;
    if (!e[i].to || !e[i^1].to) continue;
    if (e[i].to==n+1) continue;
    if (e[i^1].to==n+1) continue;
    printf("%d %d\n", e[i^1].to, e[i].to);
  }
  return 0;
}

这道题最重要的是连边。
那么很显然的拆点技巧，将一天拆成服务和收工两个点，即 i+N 和 i，后前两个点。
那么源点为 0，汇点为 2*N+1。

  • 要购买餐巾

显然从源点处购买，直接建边 add(0,i+N,inf,p)。

  • 偷懒先不洗餐巾

显然直接延到下一天，add(i,i+1,inf,0)。

  • 快洗

显然直接丢到 $m$ 天后，add(i,i+N+m,inf,f)。

  • 慢洗

同理丢到 $n$ 天后，add(i,i+N+n,inf,s)。

然后每一天要跑至少为 r[i] 的流量，直接源点连收工，汇点连服务。

然后跑一遍最小费用最大流即可。

nt 的地方：DFS 要标记 cur，数组不要开小。
要是写对了正解然后数组开小了那就真的是个 zz。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2e3 + 10;
const int inf = 2e9;

int N, cnt = 1, head[MAXN*12];
int p, m, f, n, s, dist[MAXN*12];
bool inq[MAXN*2], vis[MAXN*2];
int cost;

struct Edge {
  int to, nxt, flow, val;
} e[MAXN*12];

void addEdge(int u, int v, int f, int w) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].flow = f, e[cnt].val = w;
  head[u] = cnt;

  e[++cnt].to = u;
  e[cnt].nxt = head[v];
  e[cnt].flow = 0, e[cnt].val = -w;
  head[v] = cnt; return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

bool spfa() {
  for (int i=0; i<=2*N+1; ++i)
    dist[i] = inf, inq[i] = false;
  dist[0] = 0, inq[0] = true;
  queue <int> sp; sp.push(0);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dist[to]>dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) inq[to] = true, sp.push(to);
      }
    }
  }
  return dist[2*N+1] < inf;
}

int dfs(int cur, int Max) {
  if (cur == 2*N+1) { vis[cur] = true; return Max; }
  int increase = Max; vis[cur] = true;
  for (int i=head[cur]; i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if ((!vis[to] || to==MAXN) && e[i].flow && dist[to]==dist[cur]+e[i].val) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      cost += res * e[i].val, increase -= res;
    }
  }
  return Max-increase;
}

signed main() {
  cin >> N;
  for (int i=1; i<=N; ++i) {
    int r; cin >> r;
    addEdge(0, i, r, 0);
    addEdge(i+N, 2*N+1, r, 0);
  }
  cin >> p >> m >> f >> n >> s;
  // begin point: i
  // ending point: i+N
  for (int i=1; i<=N; ++i) {
    addEdge(0, i+N, inf, p);
    if (i<N) addEdge(i, i+1, inf, 0);
    if (i+m<=N) addEdge(i, i+N+m, inf, f);
    if (i+n<=N) addEdge(i, i+N+n, inf, s);
  }
  while (spfa()) {
    for (int i=0; i<=2*N+1; ++i) vis[i] = false;
    dfs(0, inf);
  }
  cout << cost << endl;
  return 0;
}

这道题为什么要网络流啊。

难道不是直接暴力 BFS 寻找路径吗？

直接状压一下钥匙，然后每一次到达门就看有没有钥匙就可以了。

nt 的地方：x(x), y(y) 写成了 x(x), y(x) … …

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
#include <bits/stdc++.h>
using namespace std;

const int N = 11;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int n, m, p, k, s, door[N][N][N][N];
int cnt[N][N], key[N][N][N];
bool vis[N][N][1<<N];

struct spread {
  int x, y, Key, cost;
  spread(int x, int y, int Key, int cost):
    x(x), y(y), Key(Key), cost(cost) {}
  spread() {}
};

int keyset(int x, int y) {
  int S = 0;
  for (int i=1; i<=cnt[x][y]; ++i)
    S |= (1<<(key[x][y][i]-1));
  return S;
}

bool check(int x, int y, int k, int st) {
  if (x<1 || x>n) return false;
  if (y<1 || y>m) return false;
  if (k<0 || (k && !(st&(1<<(k-1))))) return false;
  return true;
}

int bfs() {
  int x = 1, y = 1;
  int S = keyset(x, y);
  queue <spread> que; que.push(spread(x, y, S, 0));
  vis[x][y][S] = true;
  while (!que.empty()) {
    spread cur = que.front(); que.pop();
    x = cur.x, y = cur.y, S = cur.Key;
    if (x==n && y==m) return cur.cost;
    for (int i=0; i<4; ++i) {
      int tox = x + dx[i], toy = y + dy[i];
      int Door = door[x][y][tox][toy];
      if (!check(tox, toy, Door, S)) continue;
      int to = S|keyset(tox, toy);
      if (vis[tox][toy][to]) continue;
      vis[tox][toy][to] = true;
      que.push(spread(tox, toy, to, cur.cost+1));
    }
  }
  return -1;
}

int main() {
  cin >> n >> m >> p >> k;
  while (k--) {
    int x, y, X, Y, G;
    cin >> x >> y >> X >> Y >> G;
    if (G) door[x][y][X][Y] = door[X][Y][x][y] = G;
    else door[x][y][X][Y] = door[X][Y][x][y] = -1;
  }
  cin >> s;
  while (s--) {
    int x, y, Q; cin >> x >> y >> Q;
    key[x][y][++cnt[x][y]] = Q;
  }
  cout << bfs() << endl;
  return 0;
}

众所周知最小路径覆盖 $=$ 顶点数 $-$ 最大匹配数，这个是很显然的。

Proof：因为对于每一个点一开始都可以作为一条路径，所以一开始就有 $n$ 条路径。因为每一次匹配相当于把两个点合并，所以路径条数相当于减掉了 $1$，所以最大匹配数就是合并的个数，所以最后就是 $n-$最大匹配数。
又因为二分图可以网络流乱搞，所以路径覆盖也可以网络流乱搞。

所以正常的 trick，拆点跑最大流。
路径输出比较正常，直接在 DFS 的时候找到起始点然后记录路径即可。

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
#include <bits/stdc++.h>
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int N = 1e5 + 10;
const int inf = 1e9;

int n, m, s, t, cnt = 1;
int dep[N], head[N]; bool inq[N];
int cost, path[N]; bool vis[N];

struct Edge {
  int to, nxt, flow;
} e[N];

void addEdge(int u, int v, int f) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].flow = f; head[u] = cnt;

  e[++cnt].to = u;
  e[cnt].nxt = head[v];
  e[cnt].flow = 0; head[v] = cnt;
  return ;
}

bool check() {
  for (int i=0; i<=t; ++i)
    dep[i] = inf, inq[i] = false;
  dep[s] = 0; queue <int> sp;
  sp.push(s); inq[s] = true;
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dep[to]==inf) {
        dep[to] = dep[cur] + 1, sp.push(to);
      }
    }
  }
  return dep[t] ^ inf;
}

int dfs(int cur, int Max) {
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].flow && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) { dep[to] = -1; continue; }
      e[i].flow -=  res, e[i^1].flow += res;
      path[cur] = to; if (cur) vis[to-n] = true;
      increase -= res;
    }
  }
  return Max-increase;
}

int main() {
  cin >> n >> m; t = 2*n+1;
  for (int i=1; i<=m; ++i) {
    int u, v; cin >> u >> v;
    addEdge(u, n+v, 1);
  }
  for (int i=1; i<=n; ++i) addEdge(s, i, 1);
  for (int i=1; i<=n; ++i) addEdge(i+n, t, 1);
  int ans = 0; while (check()) ans += dfs(s, inf);
  for (int i=1; i<=n; ++i) {
    if (vis[i]) continue;
    int cur = i; cout << i;
    while(path[cur] && path[cur]^t)
      cout << ' ' << path[cur]-n, cur = path[cur]-n;
    cout << endl;
  }
  cout << n-ans << endl;
  return 0;
}

听名字还挺高大上的。

其实就是个卡牌游戏啊，只不过每一次只可以交换环上相邻两个。
那么直接断环成链，拿原数减掉最后的固定答案然后前缀和加到 ans。

顺带卡了下常，12ms 最优解 Rank1。

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
#include <stdio.h>
int n, sum, ans, a[110], Sum[110];

int abs(int x) { return x>0? x:-x; }

void qsort(int l, int r) {
  int mid = Sum[(l+r)>>1];
  int i=l, j=r;
  do {
    while (Sum[i]<mid) ++i;
    while (Sum[j]>mid) --j;
    if(i<=j) {
      int u=Sum[i]; Sum[i]=Sum[j]; Sum[j]=u;
      i++, j--;
    }
  } while (i<=j);
  if (l<j) qsort(l, j);
  if (i<r) qsort(i, r);
  return ;
}

int main() {
  scanf("%d", &n);
  for (int i=1; i<=n; ++i)
    scanf("%d", &a[i]), sum += a[i];
  sum /= n;
  for (int i=1; i<=n; ++i)
    Sum[i] = Sum[i-1]+a[i]-sum, a[i] = Sum[i];
  qsort(1, n); int mid = n/2+1;
  for (int i=1; i<=n; ++i)
    ans += abs(Sum[mid]-Sum[i]);
  printf("%d\n", ans);
  return 0;
}

简单题。

首先看到点有限制，直接拆点。

那么因为没有给出单源点和汇点，分别建一个。

接着可以将 * 视为连向源点，所以边权为 $1$。
同理 # 视为连向汇点，边权为限制 $p$。

然后因为 . 只能踩一次，所以拆成两个点，两个点之间的限制为 $1$。
@ 可以踩无数次，所以连 INF。

接着因为周边四个点都可以扩展到（除起始点和水显然不可以扩展）。
所以连容量为 INF 的边。

然后跑一遍最大流。

记得多测 cnt 要赋成 $1$ 而不是 $0$。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int inf = 1e9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m, p, s, t, cnt = 1;
int dep[N], head[N]; char ch[40][40];

struct Edge {
  int to, nxt, flow;
} e[N];

void addEdge(int u, int v, int f) {
  e[++cnt].to = v, e[cnt].nxt = head[u];
  e[cnt].flow = f, head[u] = cnt;
  e[++cnt].to = u, e[cnt].nxt = head[v];
  e[cnt].flow = 0, head[v] = cnt;
}

bool check(int x, int y) {
  return x<1 || x>n || y<1 || y>m;
}

void init() {
  cnt = 1; t = 2*n*m + 1;
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) cin >> ch[i][j];
  memset(head, -1, sizeof head);
  return ;
}

int id(int x, int y) { return (x-1)*m+y; }
bool spfa() {
  for (int i=s; i<=t; ++i) dep[i] = inf;
  dep[s] = 0; queue <int> sp; sp.push(s);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dep[to]==inf) {
        dep[to] = dep[cur] + 1, sp.push(to);
      }
    }
  }
  return dep[t]^inf;
}

int dfs(int cur, int Max) {
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; ~i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].flow && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      increase -= res;
    }
  }
  return Max-increase;
}

int main() {
  while (scanf("%d%d%d", &n, &m, &p) != EOF) {
    init(); int siz = n*m;
    for (int i=1; i<=n; ++i) {
      for (int j=1; j<=m; ++j) {
        if (ch[i][j] == '~') continue;
        if (ch[i][j] == '*') addEdge(s, id(i,j), 1);
        if (ch[i][j] == '.') addEdge(id(i,j), id(i,j)+siz, 1);
        if (ch[i][j] == '#') addEdge(id(i,j), t, p);
        for (int k=0; k<4; ++k) {
          int tox = i+dx[k], toy = j+dy[k];
          if (check(tox, toy)) continue;
          if (ch[tox][toy] == '*' || ch[tox][toy] == '~') continue;
          if (ch[i][j] == '.') addEdge(id(i,j)+siz, id(tox, toy), inf);
          else addEdge(id(i,j), id(tox, toy), inf);
        }
      }
    }
    int ans = 0;
    while (spfa()) ans += dfs(s, inf);
    cout << ans << endl;
  }
  return 0;
}

这题也是个拆点模板。
首先 S 连向出点，T 连向入点，默认已经拆完点。
所以因为要使得成为循环格，所以要进行两两之间点的匹配。
即入度、出度均为 $1$。

所以跑二分图匹配最小费用即可。
建边的 value 只需要看当前点实际指的方向是否是枚举的方向。
如果是费用为 $0$，否则为 $1$。

最后要注意：cnt 要赋成 $1$！！11

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
const int inf = 114514;

int n, m, s, t, cnt = 1, cost;
int dist[N], head[N];
bool vis[N], inq[N];
char Map[20][20]; int To[20][20];

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

struct Edge {
  int to, nxt, flow, val;
} e[N];

void addEdge(int u, int v, int f, int w) {
  e[++cnt].to = v, e[cnt].nxt = head[u];
  e[cnt].flow = f, e[cnt].val = w, head[u] = cnt;
  e[++cnt].to = u, e[cnt].nxt = head[v];
  e[cnt].flow = 0, e[cnt].val = -w, head[v] = cnt;
  return ;
}

bool spfa() {
  for (int i=s; i<=t; ++i)
    inq[i] = false, dist[i] = inf;
  dist[s] = 0, inq[s] = true;
  queue <int> sp; sp.push(s);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dist[to]>dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) { inq[to] = true; sp.push(to); }
      }
    }
  }
  return dist[t]^inf;
}

int dfs(int cur, int Max) {
  vis[cur] = true;
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; ~i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if ((!vis[to]||to==t) && e[i].flow && dist[to]==dist[cur]+e[i].val) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      increase -= res, cost += res * e[i].val;
    }
  }
  return Max-increase;
}

int id(int x, int y) { return (x-1)*m+y; }

int main() {
  memset(head, -1, sizeof head);
  cin >> n >> m; t = 2*n*m + 1;
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) {
      cin >> Map[i][j];
      if (Map[i][j]=='L') To[i][j] = 0;
      if (Map[i][j]=='R') To[i][j] = 1;
      if (Map[i][j]=='U') To[i][j] = 2;
      if (Map[i][j]=='D') To[i][j] = 3;
    }
  for (int i=1; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
      for (int k=0; k<4; ++k) {
        int tox = i+dx[k], toy = j+dy[k];
        if (tox<1) tox = n; if (tox>n) tox = 1;
        if (toy<1) toy = m; if (toy>m) toy = 1;
        addEdge(id(i,j)+n*m, id(tox, toy), 1, k!=To[i][j]);
      }
    }
  }
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) {
      addEdge(s, id(i,j)+n*m, 1, 0);
      addEdge(id(i,j), t, 1, 0);
    }
  int ans = 0;
  while (spfa()) {
    for (int i=s; i<=t; ++i) vis[i] = false;
    ans += dfs(s, inf);
  }
  cout << cost << endl;
  return 0;
}
Follow

Links

Categories

Recents

Archives

Tags

DS5
Graph1
Math1
Network Flows1
Number Theory2
Others2
State Compression1

Subscribe for updates

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×