Chaos Slover 补档计划 - 图的连通性

2015.12.22 15:37 Tue| 53 visits oi_2016| ChaosSlover补档计划| Text

最小树形图

POJ3164 Command Network

据说由于数据不全,手写读入会 TLE。

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

#define N 105
#define M 10005

int n, m;

struct edge
{
    int x, y; double w;
    edge() {}
    edge(int _x, int _y, double _w)
    : x(_x), y(_y), w(_w) {}
} p[M];

double edmonds(int root, int n)
{
    static double w[N];
    static int fa[N];
    static int v[N], id[N];
    double re = 0;
    while (true)
    {
        for (int i = 1; i <= n; ++i)
            w[i] = 1e99;
        memset(id, 0, sizeof id);
        memset(v, 0, sizeof v);
        w[root] = 0, fa[root] = root;
        for (int i = 1; i <= m; ++i)
            if (p[i].x != p[i].y && p[i].w < w[p[i].y])
                w[p[i].y] = p[i].w, fa[p[i].y] = p[i].x;
        for (int i = 1; i <= n; ++i)
            if (i != root)
            {
                if (w[i] == 1e99) return -1;
                re += w[i];
            }
        int tot = 0;
        for (int i = 1; i <= n; ++i)
        {
            int x = i;
            while (!v[x]) v[x] = i, x = fa[x];
            if (x == root || v[x] != i) continue;
            id[x] = ++tot;
            for (int j = fa[x]; j != x; j = fa[j]) id[j] = tot;
        }
        if (!tot) break;
        for (int i = 1; i <= n; ++i)
            if (!id[i]) id[i] = ++tot;
        for (int i = 1; i <= m; ++i)
        {
            p[i].w -= w[p[i].y];
            p[i].x = id[p[i].x], p[i].y = id[p[i].y];
            if (p[i].x == p[i].y) continue;
        }
        n = tot, root = id[root];
    }
    return re;
}

double x[N], y[N];

double dist(int a, int b)
{
    return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; ++i)
            scanf("%lf%lf", &x[i], &y[i]);
        for (int u, v, i = 1; i <= m; ++i)
            scanf("%d%d", &u, &v), p[i] = edge(u, v, dist(u, v));
        double ans = edmonds(1, n);
        if (ans == -1) puts("poor snoopy");
        else printf("%.2lf\n", ans);
    }
    return 0;
}

CF240E Road Repairs

记录路径并输出。这道题的正解并不是最小树形图,然而使用最小树形图能过,并且只需要记录 50W 条边。

 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;

#define N 100005

int n, m;
int z[N], num[5 * N];

struct edge
{
    int x, y, w, id;
    edge() {}
    edge(int _x, int _y, int _w, int _id)
    : x(_x), y(_y), w(_w), id(_id) {}
} p[N];

int edmonds(int root, int n)
{
    static int w[N], fa[N], from[N];
    static int v[N], id[N], sig[5 * N], rep[5 * N];
    int re = 0, cnt = m;
    while (true)
    {
        memset(w, 0x3f, sizeof w);
        memset(id, 0, sizeof id);
        memset(v, 0, sizeof v);
        w[root] = 0, fa[root] = root;
        for (int i = 1; i <= m; ++i)
            if (p[i].x != p[i].y && p[i].w < w[p[i].y])
                w[p[i].y] = p[i].w,
                fa[p[i].y] = p[i].x, from[p[i].y] = p[i].id;
        for (int i = 1; i <= n; ++i)
            if (i != root)
            {
                if (w[i] == 0x3f3f3f3f) return -1;
                re += w[i], ++num[from[i]];
            }
        int tot = 0;
        for (int i = 1; i <= n; ++i)
        {
            int x = i;
            while (!v[x]) v[x] = i, x = fa[x];
            if (x == root || v[x] != i) continue;
            id[x] = ++tot;
            for (int j = fa[x]; j != x; j = fa[j]) id[j] = tot;
        }
        if (!tot) break;
        for (int i = 1; i <= n; ++i)
            if (!id[i]) id[i] = ++tot;
        for (int i = 1; i <= m; ++i)
        {
            int temp = from[p[i].y];
            p[i].w -= w[p[i].y];
            p[i].x = id[p[i].x], p[i].y = id[p[i].y];
            if (p[i].x == p[i].y) continue;
            sig[++cnt] = p[i].id, rep[cnt] = temp;
            p[i].id = cnt;
        }
        n = tot, root = id[root];
    }
    for (int i = cnt; i > m; --i)
        num[sig[i]] += num[i], num[rep[i]] -= num[i];
    return re;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> n >> m;
    for (int x, y, i = 1; i <= m; ++i)
        x = read(), y = read(),
        p[i] = edge(x, y, z[i] = read(), i);
    int ans = edmonds(1, n);
    if (ans == -1) { puts("-1"); return 0; }
    cout << ans << endl;
    for (int i = 1; i <= m; ++i)
        if (z[i] && num[i])
            printf("%d ", i);
    return 0;
}

Dominator Tree

下面前两题的模板是错误的,第三题的模板已改正。

算法参见《图连通性若干拓展问题探讨》

模板解释:

tarjan 函数中第 17 行:若路径上的 best 点的半必经点时间戳不等于 fa[x],那么在 idom 中记录 best 点的位置,稍后会在 26 行更新;否则对于点 x,半必经点就是它的必经点。

SPOJBIA Bytelandian Information Agency

求有向图的割点,多组测试数据。

算法使用并查集实现。按照 DFS 序从大到小枚举每一个点,枚举之后再将其连到它在搜索树上的父亲上,这样就可以求出搜索树上 dfn 大于等于当前点的链上的点权的最小值了。

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

#define N 5005
#define M 200005

int n, m, head[N], cnt, tot;
int dfn[N], id[N], fa[N];
int f[N], best[N], semi[N], idom[N];
int ans[N];
vector<int> pre[N], dom[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void dfs(int x)
{
    dfn[x] = ++tot, id[tot] = x;
    for (int i = head[x]; i; i = edge[i].next)
        if (!dfn[edge[i].to])
            dfs(edge[i].to), fa[dfn[edge[i].to]] = dfn[x];
}

int find(int x)
{
    if (x == f[x]) return x;
    int y = find(f[x]);
    if (semi[best[f[x]]] < semi[best[x]])
        best[x] = best[f[x]];
    return f[x] = y;
}

void tarjan()
{
    for (int i = 1; i <= tot; ++i)
        f[i] = best[i] = semi[i] = i;
    for (int i = tot; i >= 2; --i)
    {
        for (auto j : pre[id[i]])
        {
            if (dfn[j] == 0) continue;
            find(dfn[j]);
            semi[i] = min(semi[i], semi[best[dfn[j]]]);
        }
        f[i] = fa[i];
        dom[semi[i]].push_back(i);
        for (auto j : dom[fa[i]])
        {
            find(j);
            if (semi[best[j]] < fa[i]) idom[j] = best[j];
            else idom[j] = fa[i];
        }
        dom[fa[i]].resize(0);
    }
    for (int i = 2; i <= tot; ++i)
    {
        if (idom[i] != semi[i]) idom[i] = idom[idom[i]];
        dom[idom[i]].push_back(i);
    }
    idom[1] = 0;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    while (cin >> n >> m)
    {
        memset(head, 0, sizeof head); cnt = 0;
        tot = 0;
        for (int i = 0; i <= n; ++i)
            pre[i].clear(), dom[i].clear();
        memset(dfn, 0, sizeof dfn);
        for (int x, y, i = 1; i <= m; ++i)
            x = read(), y = read(),
            add(x, y), pre[y].push_back(x);
        dfs(1);
        tarjan();
        memset(ans, 0, sizeof ans);
        for (int i = 1; i <= n; ++i)
            ans[id[idom[i]]] = true;
        int num = 0;
        for (int i = 1; i <= n; ++i)
            if (ans[i]) ++num;
        cout << num << endl;
        for (int i = 1; i <= n; ++i)
            if (ans[i])
                printf("%d%c", i, --num ? ' ' : '\n');
    }
    return 0;
}

SPOJEN Entrapment

建出来 dom tree 之后找到从 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
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;

#define N 300005
#define M 1000005

int test, n, m, head[N], cnt, tot;
int dfn[N], id[N], fa[N];
int f[N], best[N], semi[N], idom[N];
vector<int> pre[N], dom[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void dfs(int x)
{
    dfn[x] = ++tot, id[tot] = x;
    for (int i = head[x]; i; i = edge[i].next)
        if (!dfn[edge[i].to])
            dfs(edge[i].to), fa[dfn[edge[i].to]] = dfn[x];
}

int find(int x)
{
    if (x == f[x]) return x;
    int y = find(f[x]);
    if (semi[best[f[x]]] < semi[best[x]])
        best[x] = best[f[x]];
    return f[x] = y;
}

void tarjan()
{
    for (int i = 1; i <= n; ++i)
        f[i] = best[i] = semi[i] = i;
    for (int i = n; i >= 2; --i)
    {
        for (int j = 0; j < (int)pre[id[i]].size(); ++j)
            find(dfn[pre[id[i]][j]]),
            semi[i] = min(semi[i], semi[best[dfn[pre[id[i]][j]]]]);
        f[i] = fa[i];
        dom[semi[i]].push_back(i);
        for (int j = 0; j < (int)dom[fa[i]].size(); ++j)
            find(dom[fa[i]][j]),
            idom[dom[fa[i]][j]] = semi[best[dom[fa[i]][j]]];
        dom[fa[i]].resize(0);
    }
    for (int i = 2; i <= n; ++i)
    {
        if (idom[i] != semi[i]) idom[i] = idom[idom[i]];
        dom[idom[i]].push_back(i);
    }
    idom[1] = 0;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    while (test--)
    {
        memset(head, 0, sizeof head); cnt = 0;
        tot = 0;
        for (int i = 0; i <= n; ++i)
            pre[i].clear(), dom[i].clear();
        memset(dfn, 0, sizeof dfn);
        cin >> n >> m;
        for (int x, y, i = 1; i <= m; ++i)
            x = read(), y = read(),
            add(x, y), pre[y].push_back(x);
        dfs(1);
        tarjan();
        int ans = dfn[n];
        while (idom[ans] != 1) ans = idom[ans];
        cout << id[ans] << endl;
    }
    return 0;
}

OpenJudge1044 PKU ACM Team's Excursion

题目链接

有向图中的每一条桥边都有一个危险度,即桥边的长度。可以有两次机会坐车,每一次车乘坐的长度至多为 q,坐车通过桥边没有危险度。问从 S 走到 T 的危险度最小是多少。

首先用 dominator tree 求出桥边。由于我们必须经过所有桥边,所以可能走的路径是糖葫芦形的,其中通过糖葫芦中的每一颗山楂时,我们不妨去走最短路。这样就可以将原图转化为一维模型,用两个定长区间覆盖数轴上尽可能长的线段。有两种可能的情况:两个区间都有端点在同一个线段上或两个区间覆盖的线段互不相同。第一种情况等价于只有一个长度为 2q 的区间,第二种情况正反各扫一遍然后枚举中间点。

做完这道题,我的 dominator tree 模板就又彻底和 lyd 的模板改成一个样子了。

  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;

#define N 300005
#define M 400005
#define inf 0x3f3f3f3f

int test, n, m, s, t, len, cnt, tot, num;
int x[N], y[N], z[N], head[N], d[N];
int dfn[N], id[N], fa[N];
int f[N], best[N], semi[N], idom[N];
pair<int, int> l[N];
vector<int> pre[N], dom[N];
int sum[N], tl[N], tr[N], sl[N], sr[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void dfs(int x)
{
    dfn[x] = ++tot, id[tot] = x;
    for (int i = head[x]; i; i = edge[i].next)
        if (!dfn[edge[i].to])
            dfs(edge[i].to), fa[dfn[edge[i].to]] = dfn[x];
}

int find(int x)
{
    if (x == f[x]) return x;
    int y = find(f[x]);
    if (semi[best[f[x]]] < semi[best[x]])
        best[x] = best[f[x]];
    return f[x] = y;
}

void tarjan()
{
    for (int i = 1; i <= tot; ++i)
        f[i] = best[i] = semi[i] = i;
    for (int i = tot; i >= 2; --i)
    {
        for (int j = 0; j < (int)pre[id[i]].size(); ++j)
        {
            if (dfn[pre[id[i]][j]] == 0) continue;
            find(dfn[pre[id[i]][j]]),
            semi[i] = min(semi[i], semi[best[dfn[pre[id[i]][j]]]]);
        }
        f[i] = fa[i];
        dom[semi[i]].push_back(i);
        for (int j = 0; j < (int)dom[fa[i]].size(); ++j)
        {
            find(dom[fa[i]][j]);
            if (semi[best[dom[fa[i]][j]]] < fa[i])
                idom[dom[fa[i]][j]] = best[dom[fa[i]][j]];
            else idom[dom[fa[i]][j]] = fa[i];
        }
        dom[fa[i]].resize(0);
    }
    for (int i = 2; i <= tot; ++i)
    {
        if (idom[i] != semi[i]) idom[i] = idom[idom[i]];
        dom[idom[i]].push_back(i);
    }
    idom[1] = 0;
}

priority_queue<pair<int, int> > q;

void spfa(int s)
{
    memset(d, 0x3f, sizeof d);
    d[s] = 0; q.push(make_pair(-d[s], s));
    while (!q.empty())
    {
        int x = q.top().second, y = -q.top().first; q.pop();
        if (y != d[x]) continue;
        for (int i = head[x]; i; i = edge[i].next)
            if (d[edge[i].to] > y + edge[i].val)
                d[edge[i].to] = y + edge[i].val,
                q.push(make_pair(-d[edge[i].to], edge[i].to));
    }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    while (test--)
    {
        memset(head, 0, sizeof head); cnt = 0;
        tot = 0; num = 0;
        cin >> n >> m;
        for (int i = 0; i <= n + m; ++i)
            pre[i].clear(), dom[i].clear();
        memset(dfn, 0, sizeof dfn);
        memset(sum, 0, sizeof sum);
        memset(tl, 0, sizeof tl);
        memset(tr, 0, sizeof tr);
        memset(sl, 0, sizeof sl);
        memset(sr, 0, sizeof sr);
        s = read() + 1, t = read() + 1, len = read();
        for (int i = 1; i <= m; ++i)
            x[i] = read() + 1, y[i] = read() + 1, z[i] = read(),
            add(x[i], n + i, 0), add(n + i, y[i], z[i]),
            pre[y[i]].push_back(n + i), pre[n + i].push_back(x[i]);
        dfs(s);
        if (dfn[t] == 0) { puts("-1"); continue; }
        tarjan();
        spfa(s);
        for (int i = dfn[t]; i != 1; i = idom[i])
            if (id[i] > n)
                l[++num] = make_pair(d[x[id[i] - n]], d[y[id[i] - n]]);
        reverse(l + 1, l + num + 1);

        for (int i = 1; i <= num; ++i)
            sum[i] = sum[i - 1] - l[i].first + l[i].second;
        tl[0] = 1, tr[num + 1] = num;
        for (int i = 1; i <= num; ++i)
        {
            tl[i] = tl[i - 1];
            while (tl[i] <= i && l[i].second - l[tl[i]].second > len) ++tl[i];
            sl[i] = max(sl[i - 1],
                        sum[i] - sum[tl[i]]
                            + min(l[tl[i]].second - l[tl[i]].first,
                                  len - l[i].second + l[tl[i]].second));
        }
        for (int i = num; i; --i)
        {
            tr[i] = tr[i + 1];
            while (tr[i] >= i && l[tr[i]].first - l[i].first > len) --tr[i];
            sr[i] = max(sr[i + 1],
                        sum[tr[i] - 1] - sum[i - 1]
                            + min(l[tr[i]].second - l[tr[i]].first,
                                  len - l[tr[i]].first + l[i].first));
        }
        int ans = 0;
        for (int i = 0; i <= num; ++i)
            ans = max(ans, sl[i] + sr[i + 1]);
        tl[0] = 1;
        for (int i = 1; i <= num; ++i)
        {
            tl[i] = tl[i - 1];
            while (tl[i] <= i && l[i].second - l[tl[i]].second > len * 2) ++tl[i];
            ans = max(ans, sum[i] - sum[tl[i]]
                            + min(l[tl[i]].second - l[tl[i]].first,
                                  len * 2 - l[i].second + l[tl[i]].second));
        }
        cout << sum[num] - ans << endl;
    }
    return 0;
}

厦门双十 NOIP 模拟赛 day2t3 游走

像 a+b problem 一样在可持久化线段树上建图,再跑一遍 dominator tree。本题还有一个拓扑图的特殊限制,然而可以直接扒模板。

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

#define N 1000000

int n, a[50005], l[50005], r[50005], head[N], tot;
int dfn[N], id[N], fa[N];
int f[N], best[N], semi[N], idom[N], ans[N];
vector<int> pre[N], dom[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[2000000];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void dfs(int x)
{
    dfn[x] = ++tot, id[tot] = x;
    for (int i = head[x]; i; i = edge[i].next)
        if (!dfn[edge[i].to])
            dfs(edge[i].to), fa[dfn[edge[i].to]] = dfn[x];
}

int find(int x)
{
    if (x == f[x]) return x;
    int y = find(f[x]);
    if (semi[best[f[x]]] < semi[best[x]])
        best[x] = best[f[x]];
    return f[x] = y;
}

void tarjan()
{
    for (int i = 1; i <= tot; ++i)
        f[i] = best[i] = semi[i] = i;
    for (int i = tot; i >= 2; --i)
    {
        for (auto j : pre[id[i]])
        {
            if (dfn[j] == 0) continue;
            find(dfn[j]);
            semi[i] = min(semi[i], semi[best[dfn[j]]]);
        }
        f[i] = fa[i];
        dom[semi[i]].push_back(i);
        for (auto j : dom[fa[i]])
        {
            find(j);
            if (semi[best[j]] < fa[i]) idom[j] = best[j];
            else idom[j] = fa[i];
        }
        dom[fa[i]].resize(0);
    }
    for (int i = 2; i <= tot; ++i)
    {
        if (idom[i] != semi[i]) idom[i] = idom[idom[i]];
        dom[idom[i]].push_back(i);
    }
    idom[1] = 0;
}

void getans(int x)
{
    for (auto i : dom[x])
        ans[id[i]] = ans[id[x]] + (id[i] <= n), getans(i);
}

struct node
{
    node *son[2];
    int id;
    node(int _id = 0) : id(_id) {}
    void *operator new(size_t s);
} newnode[N], *root[50005];

int tag;

void *node::operator new(size_t s)
{
    static node *p = newnode;
    return p++;
}

void connect(int x, int y)
{
    if (y == n + 1) return;
    add(x, y);
    pre[y].push_back(x);
}

void insert(node *pre, node *&now, int l, int r, int x, int y)
{
    now = new node(++tag);
    // cout << "!!" << now->id << endl;
    now->son[0] = pre->son[0], now->son[1] = pre->son[1];
    connect(now->id, pre->id); connect(now->id, y);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) insert(pre->son[0], now->son[0], l, mid, x, y);
    else insert(pre->son[1], now->son[1], mid + 1, r, x, y);
}

void query(node *pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y) { connect(z, pos->id); return; }
    int mid = (l + r) >> 1;
    if (x <= mid) query(pos->son[0], l, mid, x, y, z);
    if (y > mid) query(pos->son[1], mid + 1, r, x, y, z);
}

int main()
{
    freopen("parade.in", "r", stdin);
    freopen("parade.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &l[i], &r[i]);
    tag = n;
    root[n + 1] = new node(++tag);
    root[n + 1]->son[0] = root[n + 1]->son[1] = root[n + 1];
    for (int i = n; i; --i)
    {
        query(root[i + 1], 1, n, l[i], r[i], i);
        insert(root[i + 1], root[i], 1, n, a[i], i);
    }
    dfs(1); tarjan();
    memset(ans, -1, sizeof ans);
    ans[1] = 1;
    getans(1);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

动态连通性问题

BZOJ4025 二分图

一个图是二分图当且仅当图上不存在一个奇环。

可以使用 LCT 维护删除时间的最大生成树,也可以分治+并查集。

分治的写法和标记永久化的线段树一模一样。把每一条边都插到维护时间的线段树中,之后按顺序搜索每一个叶子结点,叶子结点到根的链中保存的边就是在这个叶子结点表示的时刻内存在于图里的边。使用并查集按秩合并加回溯维护图的形态。至于距离的奇偶性问题,同两个点的《食物链》。

时间复杂度 O(N*log2N)。

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

#define N 100005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, m, t, fx, fy;
vector<pair<int, int> > edge[N * 4];

struct union_find_set
{
    int fa[N], size[N], c[N];
    union_find_set(int n)
    {
        for (int i = 1; i <= n; ++i)
            fa[i] = i, size[i] = 1, c[i] = 0;
    }
    int find(int x)
    {
        if (x == fa[x]) return x;
        return find(fa[x]);
    }
    int getxor(int x)
    {
        if (x == fa[x]) return 0;
        return c[x] xor getxor(fa[x]);
    }
    pair<int, int> merge(int x, int y)
    {
        if (size[fx] < size[fy]) swap(fx, fy);
        size[fx] += size[fy], fa[fy] = fx;
        c[fy] = getxor(x) xor getxor(y) xor 1;
        return make_pair(fx, fy);
    }
    void split(pair<int, int> p)
    {
        fa[p.second] = p.second;
        size[p.first] -= size[p.second];
        c[p.second] = 0;
    }
} s(0);

void insert(int pos, int l, int r, int x, int y, int u, int v)
{
    if (x <= l && r <= y)
        { edge[pos].push_back(make_pair(u, v)); return; }
    int mid = (l + r) >> 1;
    if (x <= mid) insert(lson, l, mid, x, y, u, v);
    if (y > mid) insert(rson, mid + 1, r, x, y, u, v);
}

void getans(int pos, int l, int r)
{
    stack<pair<int, int> > opt;
    int flag = false;
    for (int i = 0; i < (int)edge[pos].size(); ++i)
    {
        int x = edge[pos][i].first, y = edge[pos][i].second;
        if ((fx = s.find(x)) != (fy = s.find(y))) opt.push(s.merge(x, y));
        else if ((s.getxor(x) xor s.getxor(y)) == 0) { flag = true; break; }
    }
    int mid = (l + r) >> 1;
    if (flag) for (int i = l; i <= r; ++i) puts("No");
    else if (l == r) puts("Yes");
    else getans(lson, l, mid), getans(rson, mid + 1, r);
    while (!opt.empty())
        s.split(opt.top()), opt.pop();
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> m >> t;
    s = union_find_set(n);
    for (int u, v, x, y, i = 1; i <= m; ++i)
    {
        u = read(), v = read(), x = read(), y = read();
        insert(1, 1, n, x + 1, y, u, v);
    }
    getans(1, 1, n);
    return 0;
}

BZOJ2001 [Hnoi2010]City 城市建设

分治+并查集做法:

设当前分治结构中图为 (V,E),边权改变过的边集为 S,边权不改变的边集为 G。

Contraction:将 S 中所有边的边权设为 -INF,跑最小生成树。设最小生成树 T=(V,E'),那么 E'-S 一定全程在最小生成树中,缩点。这样可以将 |V| 缩小至 |S|+1 以下;

Reduction:将 S 中所有边的边权设为 INF,跑最小生成树。设最小生成树 T=(V,E'),那么 E-E'-S 一定全程不在最小生成树中,删掉。这样可以将 |E| 缩小至 |V|+|S|-1 以下。

这一算法的时间复杂度是 O(N*log2N) 级别的,实现上的细节就是如何记录边权改变过的边集和边权不改变的边集,这并不十分简单。我的做法是拿 vector 倒腾来倒腾去,或许不够优雅吧。

分治+LCT做法:

思路比上一种做法清晰很多。同样是一条边拆成 logQ 条插到权值线段树里面,然后拿一棵 LCT 遍历这棵线段树。需要在维护最小生成树的同时记录修改,时间复杂度也是 O(Nlog2N) 级别的。这并不需要特殊的卡常数技巧嘛,交一次就 20888ms 过了~

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

#define N 50005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, m, q, c[N];
int vis[N], pre[N], nxt[N];

struct edge
{
    int x, y, w;
    edge() {}
    edge(int _x, int _y, int _w) : x(_x), y(_y), w(_w) {}
    bool operator <(const edge &p) const { return w < p.w; }
    edge change(int x)
    {
        edge re = *this;
        re.w = c[x]; return re;
    }
} p[N];

vector<edge> g[N * 4];
vector<pair<edge, int> > s[N * 4];

struct union_find_set
{
    int fa[20005], size[20005];
    void resize(int n)
    {
        for (int i = 1; i <= n; ++i)
            fa[i] = i, size[i] = 1;
    }
    int find(int x)
    {
        if (x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }
    void merge(int x, int y)
    {
        int fx = find(x), fy = find(y);
        if (size[fx] < size[fy]) swap(fx, fy);
        size[fx] += size[fy]; fa[fy] = fx;
    }
};

union_find_set v, w;

void getans(int pos, int l, int r, int n, long long ans)
{
    v.resize(n), w.resize(n);

    if (l == r)
    {
        g[pos].push_back(s[pos][0].first.change(s[pos][0].second));
        sort(g[pos].begin(), g[pos].end());
        for (int i = 0; i < (int)g[pos].size(); ++i)
            if (w.find(g[pos][i].x) != w.find(g[pos][i].y))
                w.merge(g[pos][i].x, g[pos][i].y), ans += g[pos][i].w;
        printf("%lld\n", ans); return;
    }

    sort(s[pos].begin(), s[pos].end());
    sort(g[pos].begin(), g[pos].end());
    for (int i = 0; i < (int)s[pos].size(); ++i)
        if (w.find(s[pos][i].first.x) != w.find(s[pos][i].first.y))
            w.merge(s[pos][i].first.x, s[pos][i].first.y);
    for (int i = 0; i < (int)g[pos].size(); ++i)
        if (w.find(g[pos][i].x) != w.find(g[pos][i].y))
            w.merge(g[pos][i].x, g[pos][i].y),
            v.merge(g[pos][i].x, g[pos][i].y), ans += g[pos][i].w;

    int cnt = 0;
    static int tag[N];
    for (int i = 1; i <= n; ++i)
        if (i == v.find(i)) tag[i] = ++cnt;
    for (int i = 1; i <= n; ++i)
        tag[i] = tag[v.find(i)];

    w.resize(cnt);
    for (int i = 0; i < (int)g[pos].size(); ++i)
        if (w.find(tag[g[pos][i].x]) != w.find(tag[g[pos][i].y]))
            w.merge(tag[g[pos][i].x], tag[g[pos][i].y]),
            g[lson].push_back(
                edge(tag[g[pos][i].x], tag[g[pos][i].y], g[pos][i].w)),
            g[rson].push_back(
                edge(tag[g[pos][i].x], tag[g[pos][i].y], g[pos][i].w));

    int mid = (l + r) >> 1;
    for (int i = 0; i < (int)s[pos].size(); ++i)
    {
        s[pos][i].first.x = tag[s[pos][i].first.x];
        s[pos][i].first.y = tag[s[pos][i].first.y];
        if (s[pos][i].second <= mid)
        {
            s[lson].push_back(s[pos][i]);
            if (nxt[s[pos][i].second] > r)
                g[rson].push_back(s[pos][i].first.change(s[pos][i].second));
        }
        else
        {
            s[rson].push_back(s[pos][i]);
            if (pre[s[pos][i].second] < l)
                g[lson].push_back(s[pos][i].first);
        }
    }

    getans(lson, l, mid, cnt, ans);
    getans(rson, mid + 1, r, cnt, ans);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> m >> q;
    for (int x, y, z, i = 1; i <= m; ++i)
        x = read(), y = read(), z = read(),
        p[i] = edge(x, y, z);
    for (int x, i = 1; i <= q; ++i)
    {
        x = read(), c[i] = read();
        s[1].push_back(make_pair(p[x], i)), p[x].w = c[i];
        pre[i] = vis[x], nxt[i] = q + 1, nxt[vis[x]] = i; vis[x] = i;
    }
    for (int i = 1; i <= m; ++i)
        if (!vis[i])
            g[1].push_back(p[i]);
    getans(1, 1, q, n, 0);
    return 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
pair<int, int> addedge(int x)
{
    if (lct.getroot(e[x].x) != lct.getroot(e[x].y))
    {
        lct.link(x + n, e[x].x), lct.link(x + n, e[x].y);
        return make_pair(x, 0);
    }
    else
    {
        int y = lct.getmax(e[x].x, e[x].y) - n;
        if (e[y].z < e[x].z) return make_pair(0, 0);
        lct.cut(y + n, e[y].x), lct.cut(y + n, e[y].y);
        lct.link(x + n, e[x].x), lct.link(x + n, e[x].y);
        return make_pair(x, y);
    }
}

void goback(pair<int, int> p)
{
    if (p.first)
        lct.cut(p.first + n, e[p.first].x),
        lct.cut(p.first + n, e[p.first].y);
    if (p.second)
        lct.link(p.second + n, e[p.second].x),
        lct.link(p.second + n, e[p.second].y);
}

void insert(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y) { v[pos].push_back(z); return; }
    int mid = (l + r) >> 1;
    if (x <= mid) insert(lson, l, mid, x, y, z);
    if (y > mid) insert(rson, mid + 1, r, x, y, z);
}

void solve(int pos, int l, int r, long long ans)
{
    stack<pair<int, int> > s;
    for (int i = 0; i < (int)v[pos].size(); ++i)
        s.push(addedge(v[pos][i])),
        ans = ans + e[s.top().first].z - e[s.top().second].z;
    int mid = (l + r) >> 1;
    if (l == r) printf("%lld\n", ans);
    else solve(lson, l, mid, ans), solve(rson, mid + 1, r, ans);
    while (!s.empty())
        goback(s.top()), s.pop();
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i)
        a[i] = read(), b[i] = read(), c[i] = read(), vis[i] = 1;
    int t = read(); c[t] = read();
    for (int x, y, i = 2; i <= q; ++i)
        x = read(), y = read(), e[++tag] = edge(a[x], b[x], c[x]),
        insert(1, 1, q, vis[x], i - 1, tag), c[x] = y, vis[x] = i;
    for (int i = 1; i <= m; ++i)
        e[++tag] = edge(a[i], b[i], c[i]),
        insert(1, 1, q, vis[i], q, tag);
    for (int i = 1; i <= n; ++i)
        lct.tree[i] = new link_cut_tree::node(i, 0);
    for (int i = 1; i <= tag; ++i)
        lct.tree[n + i] = new link_cut_tree::node(n + i, e[i].z);
    solve(1, 1, q, 0);
    return 0;
}

BZOJ3563&3569 DZY Loves Chinese I&II

随便弄出来一棵生成树。给非树边设一个随机权值,设树边的权值为能覆盖这条树边的非树边权值的异或和。于是对于一个询问,如果删除的边存在一个子集,这个子集中元素的权值间异或和为 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
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;

#define N 500005
#define M 1000005

int n, m, q, head[N], vis[N], fa[N];
long long val[M];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

long long nrand()
{
    return 1ll * rand() * rand() * rand() * rand();
}

struct linear_base
{
    long long base[64];
    linear_base() { memset(base, 0, sizeof base); }
    bool insert(long long x)
    {
        for (int i = 63; i >= 0; --i)
            if ((x >> i) & 1)
            {
                if (base[i]) x ^= base[i];
                else { base[i] = x; return true; }
            }
        return false;
    }
} lb;

void dfs(int x)
{
    vis[x] = true;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
            fa[edge[i].to] = edge[i].val, dfs(edge[i].to);
        else if (edge[i].val != fa[x] && !val[edge[i].val])
            val[edge[i].val] = nrand(),
            val[fa[x]] ^= val[edge[i].val],
            val[fa[edge[i].to]] ^= val[edge[i].val];
}

void dfs2(int x)
{
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val == fa[edge[i].to])
            dfs2(edge[i].to), val[fa[x]] ^= val[edge[i].val];
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    srand(419);
    cin >> n >> m;
    for (int x, y, i = 1; i <= m; ++i)
        x = read(), y = read(), add(x, y, i), add(y, x, i);
    cin >> q;
    dfs(1);
    for (int i = 2; i <= n; ++i)
        if (!vis[i]) { while (q--) puts("Disconnected"); return 0; }
    dfs2(1);
    for (int k, ans = 0, i = 1; i <= q; ++i)
    {
        lb = linear_base();
        k = read() ^ ans;
        bool flag = false;
        for (int i = 1; i <= k; ++i)
            if (!lb.insert(val[read() ^ ans])) flag = true;
        if (flag) puts("Disconnected");
        else puts("Connected"), ++ans;
    }
    return 0;
}

Chaos Slover 补档完成度:100%...