模板——补充

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin

树上启发式合并、Kruskal 重构树、神秘康托展开、欧拉路（更新）、Dinic（更新）、cout 输出流控制。

树上启发式合并

例如计算 \(\sum_{d(x)=d(y),1\le x<y\le n}d(y)-d(lca(x,y))\)。

\(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
vector<ll> e[N];
ll a[N], d[N], cnt[N], big[N], siz[N], ans;
ll dfn[N], L[N], R[N], index;
ll n, m;

ll dfs(ll root, ll dad) {
    ll curb = 0;
    d[root] = d[dad] + 1;
    siz[root]++;
    dfn[++index] = root;
    L[root] = index;
    for (auto son: e[root]) {
        if (son == dad)
            continue;
        siz[root] += dfs(son, root);
        if (siz[son] > curb) {
            curb = siz[son];
            big[root] = son;
        }
    }
    R[root] = index;
    return siz[root];
}

void dsu(ll root, ll dad, ll keep) {
    for (auto son: e[root]) {
        if (son == dad || son == big[root])
            continue;
        dsu(son, root, 0);
    }
    if (big[root])
        dsu(big[root], root, 1);
    for (auto son: e[root]) {
        if (son == dad || son == big[root])
            continue;
        for (ll i = L[son]; i <= R[son]; i++) {
            ans += cnt[d[dfn[i]]] * (d[dfn[i]] - d[root]);
        }
        for (ll i = L[son]; i <= R[son]; i++) {
            cnt[d[dfn[i]]]++;
        }
    }
    cnt[d[root]]++;
    if (keep == 0) {
        for (ll i = L[root]; i <= R[root]; i++) {
            cnt[d[dfn[i]]]--;
        }
    }
}

Kruskal 重构树

原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。

也就是说，到点 x 的简单路径上最大边权的最小值 \(\leq val\) 的所有点 y 均在 Kruskal 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点。

注意重构树新建了节点，初始化范围为 \(n+m\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sort(h + 1, h + 1 + m, cmp);//按照边权排序
for (ll i = 1; i <= m; i++) {
    ll u = s.find(h[i].u), v = s.find(h[i].v);//并查集
    if (u != v) {
        cnt++;
        s.merge(u, cnt);
        s.merge(v, cnt);
        high[cnt] = h[i].len;//点权为边权
        e[u].push_back(cnt);
        e[cnt].push_back(u);
        e[v].push_back(cnt);
        e[cnt].push_back(v);
    }
}
dfs(cnt, cnt);

神秘康托展开

我们的目标是把全排列转化成一个变进制数，以方便我们进行加法。对于第 \(i\) 根手指，它有 \(n−i+1\) 种选择，根据位值原理，要想让每个数对应一个全排列，就要让这一位数是 \(n−i+1\) 进制的。

那么，整个过程分为三步：

  1. 将火星数变成变进制数；
  2. 将变进制数加上 \(m\)；
  3. 将变进制数变成火星数。

我们来看一个实例： 将 \(1,4,5,2,3\) 变成变进制数：

  • 首位 1 是 5 种选择 \(\{1,2,3,4,5\}\) 的第 1 种，故变为 0（从0开始）
  • 次位 4 是 4 种选择 \(\{2,3,4,5\}\) 的第 3 种，故变为 2
  • …
  • 最后，排列 \(1,4,5,2,3\) 变成了 \((02200)\)

接下来给它加上 3 变成 \((02203)\)，并处理进位：

  • 末位是 1 进制的，进 3 得 \((02230)\)。
  • 次低位是 2 进制的，满 2 进一得 \((02310)\)。
  • 中间位是 3 进制的，满 3 进一得 \((03010)\)。
  • 次位是 4 进制的，\(3<4\)，不进位，得 \((03010)\)。

最后将 \((03010)\) 变回火星数。

  • 首位 0 表示这位应选择 \(\{1,2,3,4,5\}\) 的第 1 种，即 1
  • 次位 3 表示这位应选择 \(\{2,3,4,5\}\) 的第 4 种（1 被选过了），即 5
  • …

所以本题答案为 14523 +3= 15243。

欧拉路（更新）

我们先结合定理进行分析：

  • 如果是求有没有欧拉回路：判断是有向图还是无向图，若为有向图，所有顶点出、入度相等。若为无向图，则没有奇度顶点。

  • 如果是求有没有欧拉通路：判断是有向图还是无向图，若为有向图，所有顶点的出度与入度相等或者除两个顶点外其余顶点的出度等于入度（另外两个顶点一个为入度比出度大一为起点，另外一个反之为终点）。若为无向图，仅有两个奇度顶点或者没有奇度顶点。

这里以有向图为例，求是否存在欧拉回路或者欧拉通路。

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>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 1e5 + 10, inf = 1e17;

vector<PII> e[N];
vector<ll> ans;
ll n, m, cur[N], in[N], out[N], vis[N * 2], st = 0, ed = 0;

bool cmp(PII a, PII b) {
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

void dfs(ll now) {
    for (ll &i = cur[now]; i < e[now].size(); i++) {
        if (!vis[e[now][i].second]) {
            vis[e[now][i].second] = 1;
            dfs(e[now][i].first);
        }
    }
    ans.push_back(now);
}

void solve() {
    cin >> n >> m;
    for (ll i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].push_back({v, i});
        in[v]++;
        out[u]++;
    }
    for (ll i = 1; i <= n; i++) {
        sort(e[i].begin(), e[i].end(), cmp);
        if (abs(in[i] - out[i]) > 1) {
            cout << "No" << endl;
            return;
        }
        if (out[i] - in[i] == 1) {
            if (st) {
                cout << "No" << endl;
                return;
            }
            st = i;
        }
        if (in[i] - out[i] == 1) {
            if (ed) {
                cout << "No" << endl;
                return;
            }
            ed = i;
        }
    }
    if (!st) {
        st = 1;
    }
    dfs(st);
    if (ans.size() != m + 1) {
        cout << "No" << endl;
        return;
    }
    for (auto i = ans.rbegin(); i != ans.rend(); ++i) {
        cout << *i << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

如果以无向图为例，求是否存在欧拉回路或者欧拉通路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(ll now) {
    for (ll &i = cur[now]; i < e[now].size(); i++) {
        if (!vis[e[now][i].second]) {
            vis[e[now][i].second] = 1;
            vis[e[now][i].second ^ 1] = 1;
            dfs(e[now][i].first);
        }
    }
    ans.push_back(now);
}

for (ll i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    e[u].push_back({v, i * 2});//一定要注意 2 3 是一对，4 5 是一对...
    e[v].push_back({u, i * 2 + 1});
    du[u]++;
    du[v]++;
    minn = min({minn, u, v});
}

Dinic（更新）

重点在于建模。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 2e2 + 10, inf = 1e17;

struct edge {
    ll to, val, rev;
};

ll dinicn, m, s, t, cur[N], lvl[N];
vector<edge> e[N];

ll bfs() {
    for (ll i = 1; i <= dinicn; i++) {
        lvl[i] = 0;
        cur[i] = 0;
    }
    queue<ll> q;
    q.push(s);
    lvl[s] = 1;
    while (!q.empty()) {
        ll now = q.front();
        q.pop();
        for (auto [to, val, rev] : e[now]) {
            if (val > 0 && !lvl[to]) {
                q.push(to);
                lvl[to] = lvl[now] + 1;
                if (to == t)
                    return 1;
            }
        }
    }
    return 0;
}

ll dfs(ll now, ll flow) {
    if (now == t) {
        return flow;
    }
    ll res = 0;
    for (ll &i = cur[now]; i < e[now].size(); i++) {
        auto [to, val, rev] = e[now][i];
        if (val > 0 && lvl[to] == lvl[now] + 1) {
            ll f = dfs(to, min(val, flow));
            if (f == 0) {
                lvl[to] = 0;
            }
            e[now][i].val -= f;
            e[to][rev].val += f;
            res += f;
            flow -= f;
        }
    }
    return res;
}

void add(ll a, ll b, ll c) {
    e[a].push_back((edge){b, c, e[b].size()});
    e[b].push_back((edge){a, 0, e[a].size() - 1});
}

void solve() {
    ll ans = 0;
    cin >> dinicn >> m >> s >> t;
    for (ll i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e[u].push_back((edge){v, w, e[v].size()});
        e[v].push_back((edge){u, 0, e[u].size() - 1});
    }
    while (bfs()) {
        ans += dfs(s, inf);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

cout 输出流控制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n = 141;
   // 1）分别以十六进制、十进制、八进制先后输出n
   cout << "1)" << hex << n << " " << dec << n << " " << oct << n << endl;
   double x = 1234567.89, y = 12.34567;
   // 2)保留5位有效数字
   cout << "2)" << setprecision(5) << x << " " << y << " " << endl;
   // 3)保留小数点后面5位
   cout << "3)" << fixed << setprecision(5) << x << " " << y << endl;
   // 4)科学计数法输出，且保留小数点后面5位
   cout << "4)" << scientific << setprecision(5) << x << " " << y << endl;
   // 5）非负数显示正号，输出宽度为12字符，宽度不足则用*填补
   cout << "5)" << showpos << fixed << setw(12) << setfill('*') << 12.1 << endl;
   // 6）非负数不显示正号，输出宽度为12字符，宽度不足则右边用填充字符填充
   cout << "6)" << noshowpos << setw(12) << left << 12.1 << endl;
   // 7）输出宽度为12字符，宽度不足则左边用填充字符填充
   cout << "7)" << setw(12) << right << 12.1 << endl;
   // 8）宽度不足时，负号和数值分列左右，中间用填充字符填充
   cout << "8)" << setw(12) << internal << -12.1 << endl;
   cout << "9)" << 12.1 << endl;