ACM►二分

CodeForces740D - Alyona and a tree (二分+树上差分)

题目链接：

http://codeforces.com/problemset/problem/740/D

题目大意：

给出一颗有根树，每个点有点权$a_i$，每个边有边权，定义$dist(u, v)$为 u 到 v 的边权和，如果有两个节点符合，v 是 u 的子节点并且 $dist(u, v) \le a_v$那么称 v 为 u 控制的节点。

题目要求输出每个点控制的节点有多少个。

解题过程：

大体思路没错，推出来如果固定 v 的话，那么从 v 往上会有一段连续的祖先都可以控制 v，让他们控制的节点都加一就可以了，然后找这一段连续的祖先可以用二分去找。但是不知道该怎么让这一对祖先同时加一，于是想起来之前刚学的树链剖分，感觉 CF div2 的 D 题不至于上树剖…

然后去翻了下博客，发现了居然还有树上差分这种东西！问了学长 + 翻了 standing 上的代码算是理解了。

题目分析：

首先我们设 $dep[u] $ 为根节点到节点 u 的权值和，对于原式 $dist(u, v) \le a_v$ 可化为 $dep[v] - a_v \le dep[u]$ ，这样我们在递归到 v 的时候，维护一个序列以深度的顺序记录 v 的所有祖先的 $dep$ 值，然后这个值肯定是递增的。

这样对于每个节点 v 用二分在序列里找到满足上式最小的$dep[u]$，那么序列中 u 后面的节点都满足上式，让这些节点控制的节点数全加一即可。

对于加一这个操作，我们让第一个祖先节点的父亲减一，当前节点的父亲加一，然后你会会发现，现在每个节点的所有子节点和他自身的和就是答案了。

AC代码：

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

using namespace std;

typedef long long LL;

const int MAX = 212345;

int n, idx[MAX], pcnt;
//pre记录当前节点所有父亲节点的dep，并且是递增的
//idx记录pre数组里每个位置对应的下标
//d记录当前节点+1/-1操作了多少次
//ans记录答案
LL a[MAX], w[MAX], pre[MAX], d[MAX], ans[MAX];

vector<int> G[MAX];

void dfs(int u) {
	//找出第一个符合的祖先
    int id = lower_bound(pre, pre + pcnt + 1, pre[pcnt] - a[u]) - pre;
    //进行+1/-1操作
    d[idx[id - 1]]--;
    d[idx[pcnt - 1]]++;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        //更新pre数组
        pre[pcnt + 1] = pre[pcnt] + w[v];
        idx[pcnt + 1] = v;
        pcnt++;
        dfs(v);
        pcnt--;
        //累加每个儿子的权值和
        ans[u] += ans[v];
    }
    ans[u] += d[u];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int v = 2; v <= n; v++) {
        int u;
        scanf("%d%lld", &u, &w[v]);
        G[u].push_back(v);
    }
    idx[0] = 1;
    dfs(1);
    for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
}
ACM►图论►连通性

POJ3694 - Network（强连通+LCA）

题目链接：

http://poj.org/problem?id=3694

题目大意：

给出一个无向图。

有 q 次操作，每次增加一条边，询问图中有多少桥。

q < 1e3, n < 1e5, m < 2e5

解题过程：

不会写，思路到是有，不知道该怎么维护一条路径上的点，并让其缩点成一个点，到时想起来了树链剖分（昨天刚写了一个模板）。

想法是缩成树型图，每个边权值为1，增加一条边就让路径上的所有边的边权置零，每次输出整棵树的权值和即可。

感觉太麻烦了，于是偷偷去看了下讨论区，发现用 LCA（最近公共祖先） 加并查集就很容易解决这个问题

题目分析：

首先缩点成树形图，对于每一次操作，新加的一条边 (u, v) ，让 u，v 两点确定的路径上的所有点的用并查集缩成一个点（包括u，v），缩成的点为u，v的LCA，这样缩掉几个点，原图就减少了几个桥。用一个值来维护答案即可。

AC代码：

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
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAX = 100000 + 10;

int n, m, q, Case, sum;
int head[MAX], etot;
int deep[MAX], f[MAX], fa[MAX];
int pre[MAX], low[MAX], mark[MAX], dfs_clock, scc_cnt;
stack<int> S;

struct Edge {
    int u, v, nxt;
} edge[MAX << 4];

void add_edge(int u, int v) {
    edge[etot].v = v;
    edge[etot].u = u;
    edge[etot].nxt = head[u];
    head[u] = etot++;
}

void dfs(int u, int fat) {
    pre[u] = low[u] = ++dfs_clock;
    S.push(u);
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (!pre[v]) {
            dfs(v, i);
            low[u] = min(low[u], low[v]);
        } else if (i != (fat^1)) {
            low[u] = min(low[u], pre[v]);
        }
    }
    if (low[u] == pre[u]) {
        int x;
        scc_cnt++;
        do {
            x = S.top();
            S.pop();
            mark[x] = scc_cnt;
        } while (x != u);
    }
}

void init() {
    memset(pre, 0, sizeof(pre));
    memset(mark, 0, sizeof(mark));
    memset(head, -1, sizeof(head));
    scc_cnt = dfs_clock = sum = etot = 0;
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
}

void tarjan() {
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) dfs(i, -1);
    }
}

void get_deep(int u, int fat, int dep) {
    deep[u] = dep, f[u] = u;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v != fat) {
            fa[v] = u;
            get_deep(v, u, dep + 1);
            sum++;
        }
    }
}

void rebuild() {
    int tail = etot;
    memset(head, -1, sizeof(head));
    for (int i = 0; i < tail; i++) {
        int u = edge[i].u;
        int v = edge[i].v;
        if (mark[u] != mark[v]) {
            add_edge(mark[u], mark[v]);
        }
    }
}

int root(int t) {
    if (t == f[t]) return t;
    return f[t] = root(f[t]);
}

void lca(int u, int v) {
    u = root(u), v = root(v);
    stack<int> st;
    //循环直到找到公共祖先
    while (u != v) {
        //让u为较深的节点
        if (deep[u] < deep[v]) swap(u, v);
        //通过减少的节点数维护答案
        sum--;
        st.push(u);
        //让u爬到他的父亲节点
        u = root(fa[u]);
    }

    //最后让路径上经过的点都缩成LCA一个点
    while (!st.empty()) {
        f[st.top()] = u;
        st.pop();
    }
}

void solve() {
    //边双连通划分+缩点
    tarjan();
    rebuild();

    //获得新图的每个点的深度和父亲
    get_deep(1, -1, 1);

    printf("Case %d:\n", ++Case);

    scanf("%d", &q);
    while (q--) {
        int u, v;
        scanf("%d %d", &u, &v);
        //对每次操作通过并查集缩点
        lca(mark[u], mark[v]);
        printf("%d\n", sum);
    }
}

int main() {
    while (~scanf("%d %d", &n, &m) && (n + m)) {
        init();
        solve();
    }
}
ACM►数据结构►树链剖分

HDU3966 - Aragorn's Story（树链剖分+模板）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3966

题目大意：

给出一颗树，每个点有点权。
两种操作：

  1. 询问一个点的权值。
  2. 令一条路径上的所有点权值加value

点数5e4

解题过程：

线段树的模板题，拿着学长的板子直接上了，结果又RE了，没改MAX大小…
然后又交了一发TLE，用来存边的vector没初始化…
然后又交了一发WA，push_down的时候直接把子节点的lazy标记覆盖了（这个地方不知道错了多少次了！！！）

题目分析：

树链剖分的模板题

总的来说树链剖分就是一个工具，可以把一个路径上的点映射成几段连续的区间上。这样对于连续的区间可以用线段树维护，对于DFS序也是这样。

AC代码：

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
174
175
176
177
178
#include <bits/stdc++.h>

#define lson o<<1
#define rson o<<1|1
#define MID int m = (l+r)/2

using namespace std;

const int MAX = 50000 + 10;
const int INF = 0x3f3f3f3f;

struct Info {
    int sum, lazy, cnt;

    Info() {
        sum = lazy = cnt = 0;
    }

    Info operator+(const Info &a) {
        Info rst;
        rst.sum = sum + a.sum;
        rst.cnt = cnt + a.cnt;
        return rst;
    }
} tree[MAX << 2];

vector<int> edge[MAX];
int data[MAX], n, m, p;
char str[112];

int id_data[MAX];
int fa[MAX], son[MAX], siz[MAX];
int deep[MAX], top[MAX], tid[MAX];
int _cnt;

void build(int o, int l, int r) {
    tree[o].lazy = 0;
    if (l == r) {
        tree[o].sum = id_data[l];
        tree[o].cnt = 1;
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m + 1, r);
    tree[o] = tree[lson] + tree[rson];
}

void push_down(int o) {
    if (!tree[o].lazy) return;
    int lazy = tree[o].lazy;
    tree[lson].lazy += lazy;
    tree[rson].lazy += lazy;
    tree[lson].sum += lazy * tree[lson].cnt;
    tree[rson].sum += lazy * tree[rson].cnt;
    tree[o].lazy = 0;
}

void updata(int o, int l, int r, int ul, int ur, int d) {
    if (r < ul || ur < l) return;
    if (ul <= l && r <= ur) {
        tree[o].sum += tree[o].cnt * d;
        tree[o].lazy += d;
        return;
    }
    push_down(o);
    MID;
    updata(lson, l, m, ul, ur, d);
    updata(rson, m + 1, r, ul, ur, d);
    tree[o] = tree[lson] + tree[rson];
}

Info query(int o, int l, int r, int pos) {
    if (r < pos || pos < l) return Info();
    if (l == r) {
        return tree[o];
    }
    push_down(o);
    MID;
    return query(lson, l, m, pos) + query(rson, m + 1, r, pos);
}

//第一次dfs记录信息
void dffs(int u, int f, int d) {
    siz[u] = 1, deep[u] = d;
    fa[u] = f, son[u] = -1;
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i];
        if (v != f) {
            dffs(v, u, d + 1);
            siz[u] += siz[v];
            if (son[u] == -1 || siz[son[u]] < siz[v]) {
                son[u] = v;
            }
        }
    }
}

//第二次dfs找出重链，进行剖分
void dfss(int u, int t) {
    top[u] = t, tid[u] = _cnt++;
    id_data[_cnt - 1] = data[u];
    if (son[u] != -1) dfss(son[u], t);
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i];
        if (son[u] != v && fa[u] != v) dfss(v, v);
    }
}

void splite() {
    _cnt = 1;
    dffs(1, -1, 0);
    dfss(1, 1);
}

void Updata(int x, int y, int d) {
    int tx = top[x], ty = top[y];
    while (tx != ty) {
        if (deep[tx] < deep[ty]) swap(x, y), swap(tx, ty);
        updata(1, 1, n, tid[tx], tid[x], d);
        x = fa[tx], tx = top[x];
    }
    if (deep[x] < deep[y]) swap(x, y);
    updata(1, 1, n, tid[y], tid[x], d);
}

//Info Query(int x, int y) {
//    Info ix, iy;
//    int tx = top[x], ty = top[y];
//    while (tx != ty) {
//        if (deep[tx] < deep[ty]) swap(x, y), swap(tx, ty), swap(ix, iy);
//        ix = query(1, 1, n, tid[tx], tid[x]) + ix;
//        x = fa[tx], tx = top[x];
//    }
//    if (deep[x] < deep[y]) swap(x, y);
//    return ix + query(1, 1, n, tid[y], tid[x]) + iy;
//}

void init() {
    for (int i = 1; i <= n; i++) {
        scanf("%d", &data[i]);
        edge[i].clear();
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
}


void solve() {
    splite();
    build(1, 1, n);
    while (p--) {
        int a, b, c;
        scanf("%s", str);
        if (str[0] == 'Q') {
            scanf("%d", &a);
            printf("%d\n", query(1, 1, n, tid[a]).sum);
        } else {
            scanf("%d %d %d", &a, &b, &c);
            if (str[0] == 'I') {
                Updata(a, b, c);
            } else {
                Updata(a, b, -c);
            }
        }
    }
}

int main() {
    while (~scanf("%d %d %d", &n, &m, &p)) {
        init();
        solve();
    }
}
ACM►图论►网络流

HDU4289 - Control（最大流最小割）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4289

题目大意：

给出一个无向图，每个点有点权，要删除一些点使得A、B两点不再连通，问最小权值和。

解题过程：

想到大概是网络流，但是不知道该怎么建图，最后没做出来，看了题解后才发现，原来花费可以和容量交换一下….

题目分析：

对于每个点拆成入点和出点，中间建一条容量为点权的边。
对原图的无向边(u,v)对u的出点建一条到v的入点边，对v的出点建一条到u的入点的边，容量为无穷大。

这样问题就转化为，要用一些点的入点和出点之间的边去阻塞路径，阻塞所需要的流量就是所需要的花费，要最小花费就是求最小割。

AC代码：

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

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1000;
const int INF = 0x3f3f3f3f;

struct Node {
    int v, nxt, cap;
} edge[MAX * MAX];

int head[MAX], etot;
int level[MAX];

void add_edge(int u, int v, int cap1) {
    edge[etot].v = v;
    edge[etot].cap = cap1;
    edge[etot].nxt = head[u];
    head[u] = etot++;

    edge[etot].v = u;
    edge[etot].cap = 0;
    edge[etot].nxt = head[v];
    head[v] = etot++;
}

bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    q.push(s);
    level[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].v;
            int cap = edge[i].cap;
            if (cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] != -1;
}

int dfs(int u, int end, int f) {
    if (u == end) return f;
    int flow = 0, d;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        int cap = edge[i].cap;
        if (cap > 0 && level[v] > level[u] && (d = dfs(v, end, min(f, cap)))) {
            edge[i].cap -= d;
            edge[i ^ 1].cap += d;
            flow += d;
            f -= d;
            if (!f) break;
        }
    }
    if (flow == 0) level[u] = -1;
    return flow;
}

int max_flow(int s, int t) {
    int flow = 0;
    while (bfs(s, t)) {
        flow += dfs(s, t, INF);
    }
    return flow;
}

int main() {
    int n, m, s, t;
    while (~scanf("%d %d", &n, &m)) {
        memset(head, -1, sizeof(head));
        etot = 0;
        scanf("%d %d", &s, &t);

        for (int i = 1; i <= n; i++) {
            int cost;
            scanf("%d", &cost);
            //对入点和出点建边，费用为点权
            add_edge(i, i + n, cost);
        }

        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            //对原图的边建两条容量为无穷大的边
            add_edge(u + n, v, INF);
            add_edge(v + n, u, INF);
        }

        //求得的最小割即为答案
        printf("%d\n", max_flow(s, t + n));
    }
}
ACM►数据结构►线段树

HDU4288 - Coder（线段树）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4288

题目大意：

给出一个有小到大排序的集合，初始化为空。

三种操作：

  1. 插入一个数。
  2. 删除一个数。
  3. 询问 $\sum_{1 \le i \le k} a_i, \text{where} i \mod 5 = 3$

解题过程：

当初好多人都是暴力水过去的，然后刚开始看错了题意，然后试了好多次都不行…
然后重新写暴力TLE，最后没时间也放弃了，比赛后就直接用线段树去补了。

题目分析：

由于集合是有序的，先离散化输入的数据，用线段树去维护这个列表。

用线段树去维护两个值，一个是线段树当前区间内已经插入的数字个数，一个是区间内下标%5分别等于0~4的已插入的元素的和。

然后合并的时候父节点的sum[i] = sum1[i] + sum2[((i-cnt1)%5+5)%5]，cnt1为左儿子插入的元素个数。

AC代码：

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

using namespace std;

typedef long long ll;

const int MAX = 112345;

#define lson o<<1
#define rson o<<1|1
#define MID int m = (l + r) >> 1

struct Node {
    ll sum[5];
    int cnt;
} tree[MAX<<2];

void merge(int o) {
    //进行合并，可以理解成，左儿子插入过了几个元素，右儿子要找的位置就要向左移几次
    for (int i = 0; i < 5; i++) {
        tree[o].sum[i] = tree[lson].sum[i]
                         + tree[rson].sum[((i - tree[lson].cnt) % 5 + 5) % 5];
    }
}

void build(int o, int l, int r) {
    tree[o].cnt = 0;
    memset(tree[o].sum, 0, sizeof(tree[o].sum));
    if (l == r) return;
    MID;
    build(lson, l, m);
    build(rson, m + 1, r);
}

void updata(int o, int l, int r, int pos, int v) {
    if (r < pos || pos < l) return;
    //记录插入的元素个数
    tree[o].cnt += v > 0 ? 1 : -1;
    if (l == r) {
        //区间长度为1时，只有下标%5=1的元素
        tree[o].sum[1] += v;
        return;
    }
    MID;
    updata(lson, l, m, pos, v);
    updata(rson, m + 1, r, pos, v);
    merge(o);
}

int n;
char op[MAX][112];
int tmp[MAX], data[MAX];

int main() {
    while (~scanf("%d", &n)) {
        int num = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s", op[i]);
            if (op[i][0] != 's') {
                scanf("%d", &data[i]);
                tmp[num++] = data[i];
            }
        }
        //对插入的元素进行离散化
        sort(tmp, tmp + num);
        num = unique(tmp, tmp + num) - tmp;
        build(1, 1, num);
        for (int i = 0; i < n; i++) {
            int pos = lower_bound(tmp, tmp + num, data[i]) - tmp + 1;
            if (op[i][0] == 'a') updata(1, 1, num, pos, data[i]);
            if (op[i][0] == 'd') updata(1, 1, num, pos, -data[i]);
            //每次询问整个区间下标%5=3的和
            if (op[i][0] == 's') printf("%lld\n", tree[1].sum[3]);
        }
    }
}
ACM►二分

HDU6070 - Dirt Ratio（线段树+二分答案）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6070

题目大意：

给出一个序列A，对于序列里面的每一个数字范围为1～n，要求找出一段连续子序列，Y为区间长度，X为区间不同数字的个数，使得X/Y尽量的小。

解题过程：

多校赛的第四题，也算是A题比较快的一场，最后卡在了这个题上，感觉可以做的，但是不会。只想到了线段树，完全没往二分上面想，听说有$O(N^2)$卡过去的。第一次遇到这样固定一个区间边界的线段树题。

题目分析：

首先X是肯定小于等于Y，那么答案的范围一定为[0~1]，这个题是特判，精度误差在$10^{-4}$就可以，这样二分答案只需要20次左右。

对于二分答案就是检查当前线段树上是否有一个区间，使得
$$ \frac {size(l, r)} {r-l+1} \leq mid$$
$$ size(l, r) + l \times mid \leq mid \times (r + 1)$$

上述的size(l, r)为[l, r]内不同数字的个数

这么我们在线段树上维护左边的值，每次在线段树上查询是否有一段区间满足上述公式。

对于线段树上的每一个节点，假设维护的区间为$(a, b)$，那么维护的信息为$min(size(i, r) + l \times mid), a \ge i \le b$。

由于我们相当于固定住了r这个边界，对r从1～n开始枚举，对于每次对线段树新插入一个数x，假设x上一次出现的位置为p，当前插入的位置为r，那么只对 $(p+1,r]$这段区间内的size值有影响，需要加一。

另外在查询的时候，要保证查询的区间的右边界都要小于当前枚举到的r。

AC代码：

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

#define root 1, 1, n
#define lson o<<1
#define rson o<<1|1
#define MID int m = (l+r)/2

using namespace std;

const int MAX = 60000 + 10;

struct Node {
    int lazy;
    double v;
} tree[MAX << 2];

int data[MAX], Case, n, last[MAX];
double M;

inline void tag(int o, int p) { tree[o].lazy += p, tree[o].v += p; }

inline void push_down(int o) {
    if (tree[o].lazy) { tag(lson, tree[o].lazy), tag(rson, tree[o].lazy), tree[o].lazy = 0; }
}

void merge(int o) {
    //更新根节点的最小值
    tree[o].v = min(tree[lson].v, tree[rson].v);
}

void build(int o, int l, int r) {
    //初始化假设区间内不同的数字为0
    tree[o].v = M * l;
    tree[o].lazy = 0;
    if (l == r) return;
    MID;
    build(lson, l, m);
    build(rson, m + 1, r);
}

void updata(int o, int l, int r, int ul, int ur) {
    if (ul > r || l > ur) return;
    if (ul <= l && r <= ur) {
        //区间内不同数字的数量加一
        tag(o, 1); return;
    }
    push_down(o);
    MID;
    updata(lson, l, m, ul, ur);
    updata(rson, m + 1, r, ul, ur);
    merge(o);
}

double query(int o, int l, int r, int pos) {
    //进行剪枝
    if (l > pos) return 1e9;
    //必须当前的右边界小于pos才能返回答案
    if (r <= pos) {
        return tree[o].v;
    }
    push_down(o);
    MID;
    return min(query(lson, l, m, pos), query(rson, m + 1, r, pos));
}

int main() {
    scanf("%d", &Case);
    while (Case--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", data + i);
        double L = 0, R = 1;
        //最多需要二分20次
        for (int times = 0; times < 20; times++) {
            M = (L + R) / 2;
            build(root);
            for (int i = 1; i <= n; i++) last[i] = 0;
            bool ok = false;
            for (int i = 1; i <= n; i++) {
                //last表示data[i]上一次出现的位置
                updata(root, last[data[i]] + 1, i);
                //t表示能找到的size(l,r)+mid*l的最小值
                double t = query(root, i);
                if (t - M * (i + 1) <= 0) { ok = true; break; };
                last[data[i]] = i;
            }
            if (ok) R = M;
            else L = M;
        }
        printf("%f\n", (L + R) / 2);
    }
}
ACM►图论►连通性

HDU2242 - 考研路茫茫——空调教室（边双连通+树型DP）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2242

题目大意：

给出一个连通的无向图，要求删除一条边使得无向图变为两个连通分量，每个点有一个权值$A_i$，使得两连通分量的权值差最小。

解题过程：

拿来练手的题，看了一堆树和博客，这题主要是要处理重边比较麻烦，对于无向图的边双连通，其实和有向图的强连通的处理方式差不多。单纯的将边双连通分量标记好就可以了，每个点只属于一个边双连通分量。

另外比较重要是，对无向图进行双连通缩点后，所剩下的图是一个树形图！

题目分析：

首先缩点成树形图，缩后点的权值为包含所有点的和。然后用树型DP求每个节点及其儿子的权值和。

这时对于树型图，剩下的每一条边都是桥。那么枚举每一个点，假设删去它与它父亲之间的边。那么拆成的两个连通分量的权值差为$ABS(\sum_{i=0}^{n}A_i - DP_i)$，$DP_i$为$i$节点及其儿子节点的权值和。这里缩点后是一个无根树，任意找一个点作为根节点即可。

AC代码：

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

using namespace std;

const int MAX = 10000 + 10;

struct Edge {
    int v, nxt;
} edge[MAX << 2];

int n, m, data[MAX], sum;

int head[MAX], ecnt;
vector<int> G[MAX];

int dfs_clock, scc_cnt;
int low[MAX], pre[MAX], mark[MAX];
stack<int> S;

int dp[MAX];

void add_edge(int u, int v) {
    edge[ecnt].v = v;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

void init() {
    dfs_clock = scc_cnt = sum = ecnt = 0;
    memset(head, -1, sizeof(head));
    memset(pre, 0, sizeof(pre));
    memset(mark, 0, sizeof(mark));
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= n; i++) {
        G[i].clear();
    }

    for (int i = 0; i < n; i++) {
        scanf("%d", data + i);
        sum += data[i];
    }

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
}


//无向图边双连通和有向图的强连通神似
void tarjan(int u, int fa) {
    low[u] = pre[u] = ++dfs_clock;
    S.push(u);

    for (int i = head[u]; ~i; i = edge[i].nxt) {
        //这里不直接用v != fa来做判断，是为了避免重边的情况
        if (i == (fa ^ 1)) continue;
        int v = edge[i].v;
        if (!pre[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
        }
        if (!mark[v]) {
            low[u] = min(low[u], pre[v]);
        }
    }
    if (pre[u] == low[u]) {
        scc_cnt++;
        int x;
        do {
            x = S.top(); S.pop();
            mark[x] = scc_cnt;
            dp[scc_cnt] += data[x];
        } while (x != u);
    }
}

void rebuild() {
    for (int u = 0; u < n; u++) {
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].v;
            if (mark[u] != mark[v]) G[mark[u]].push_back(mark[v]);
        }
    }
}

//树型DP求权值和
int dfs(int u, int fat) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fat) continue;
        dfs(v, u);
        dp[u] += dp[v];
    }
}

void solve() {
    for (int i = 0; i < n; i++) {
        if (!pre[i]) tarjan(i, -1);
    }
    if (scc_cnt == 1) { puts("impossible"); return; }
    rebuild();
    dfs(1, -1);
    int ans = 1e9;
    for (int i = 1; i <= scc_cnt; i++) {
        ans = min(ans, abs(sum - dp[i] * 2));
    }
    printf("%d\n", ans);
}

int main() {
    while (~scanf("%d %d", &n, &m) && n) {
        init();
        solve();
    }
}
ACM►图论►连通性

HDU3639 - Hawk-and-Chicken（强连通+缩点）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3639

题目大意：

给出一个有向图，记每个点的值为他的子节点的个数，求出最大的值为多少，有那些顶点值最大。

解题过程：

题意刚开始理解错了…以为一个点可以贡献多次。

题目分析：

这题写出来主要是提醒自己一下，在DAG上不能直接用一个点维护他所有子节点权值和那样的东西，因为DAG上一个点可以有多个父亲，不像树形图那样。

另外这个题，只需要统计入度为0的点就可以了，刚开始要方向建图，这样dfs的时候才符合他的子节点贡献给父亲节点。

AC代码：

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

using namespace std;

const int MAX = 5000 + 10;

int T, n, m, Case;

vector<int> G1[MAX], G2[MAX];

int pre[MAX], low[MAX], mark[MAX], dfs_clock, scc_cnt;
stack<int> S;

int self_supports[MAX], dp[MAX], in[MAX];
bool winner[MAX];

void tarjan(int u) {
    pre[u] = low[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G1[u].size(); i++) {
        int v = G1[u][i];
        if (!pre[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        if (!mark[v]) {
            low[u] = min(low[u], pre[v]);
        }
    }
    if (low[u] == pre[u]) {
        scc_cnt++;
        int x;
        do {
            x = S.top();
            S.pop();
            mark[x] = scc_cnt;
        } while (x != u);
    }
}

void get_G() {
    for (int i = 1; i <= n; i++) {
        self_supports[mark[i]]++;
    }
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < G1[u].size(); i++) {
            int v = G1[u][i];
            if (mark[u] != mark[v]) {
                G2[mark[u]].push_back(mark[v]);
                in[mark[v]]++;
            }
        }
    }
}

void init() {
    scanf("%d %d", &n, &m);
    dfs_clock = scc_cnt = 0;
    memset(pre, 0, sizeof(pre));
    memset(mark, 0, sizeof(mark));
    memset(winner, 0, sizeof(winner));
    memset(dp, -1, sizeof(dp));
    memset(in, 0, sizeof(in));
    memset(self_supports, 0, sizeof(self_supports));
    for (int i = 0; i <= n; i++) {
        G1[i].clear();
        G2[i].clear();
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u++, v++;
        G1[v].push_back(u);
    }
}

int dfs(int u) {
    int ans = self_supports[u] - 1;
    pre[u] = 1;
    for (int i = 0; i < G2[u].size(); i++) {
        int v = G2[u][i];
        if (!pre[v]) {
            ans += dfs(v) + 1;
        }
    }
    return ans;
}

void solve() {
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) tarjan(i);
    }
    get_G();
    int ans = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (in[i] != 0) continue;
        memset(pre, 0, sizeof(pre));
        dp[i] = dfs(i);
        ans = max(dp[i], ans);
    }
    for (int i = 1; i <= scc_cnt; i++) {
        if (dp[i] == ans) winner[i] = true;
    }
    bool fir = true;
    printf("Case %d: %d\n", ++Case, ans);
    for (int i = 1; i <= n; i++) {
        if (winner[mark[i]]) {
            if (!fir) putchar(' ');
            printf("%d", i - 1);
            fir = false;
        }
    }
    putchar('\n');
}

int main() {
    scanf("%d", &T);
    while (T--) {
        init();
        solve();
    }
}
ACM►图论►连通性

HDU3861 - The King’s Problem（强连通+缩点+匈牙利）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3861

题目大意：

给出一个有向图，想在要把无向图分成k个部分，对于每对可以互相到达的(u, v)要属于同一个部分，另外每个部分中任意两个点(u, v)至少可以由u到达v或者由v到达u。

解题过程：

刚开始一点都不会，还看错了题意，只知道可以缩成DAG，但是缩完也不知道该怎么搞，只好去翻了下博客，发现缩完点，要求的就是最小路径覆盖，然后最小路径覆盖需要用到二分图匹配，顺手去学了一下匈牙利。

不过匈牙利刚开始没仔细看，学的曲线有点歪…回来才弄明白。

题目分析：

首先对原图强连通分量分解，缩点转化为DAG图。然后分析一下，题目说描述的就是最小路径覆盖。

一个有向图中，路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联

对于DAG的最小路径覆盖就是DAG的顶点数减去DAG对应的二分图的最大匹配数。

这篇博客 讲的就非常好，也有必要的证明。

需要补充一下的就是代码部分了，这个代码写的有点强，虽然说上面的分析讲到要对DAG的每个点拆成两个点建图，然后跑最大二分图匹配。但是代码上并没有拆点。

使用匈牙利匹配的时候，DFS函数里面从u匹配到v时，只对v进行标记一下，这样虽然u已经匹配了，但是他还可以当做入点再匹配一次。这样也相当于拆点建图了。对于每个点当做入点被匹配和当做出点被匹配是相对独立的，正好符合上面描述的算法。

不过这里老老实实的拆点再匹配也可以AC，就是相对于上面的代码麻烦点了。

AC代码：

不拆点

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

using namespace std;

const int MAX = 5000 + 10;

vector<int> G1[MAX], G2[2 * MAX];

int n, m, T;

int pre[MAX], low[MAX], mark[MAX], dfs_clock, scc_cnt;
stack<int> S;

int check[2 * MAX], matching[2 * MAX];

void tarjan(int u) {
    low[u] = pre[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G1[u].size(); i++) {
        int v = G1[u][i];
        if (!pre[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        if (!mark[v]) {
            low[u] = min(low[u], pre[v]);
        }
    }
    if (low[u] == pre[u]) {
        ++scc_cnt;
        int x;
        do {
            x = S.top();
            S.pop();
            mark[x] = scc_cnt;
        } while (x != u);
    }
}

void init() {
    memset(pre, 0, sizeof(pre));
    memset(mark, 0, sizeof(mark));
    scc_cnt = dfs_clock = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) G1[i].clear();
    for (int i = 1; i <= 2 * n; i++) G2[i].clear();
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G1[u].push_back(v);
    }
}

void rebuild() {
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < G1[u].size(); i++) {
            int v = G1[u][i];
            if (mark[u] != mark[v]) {
                G2[mark[u]].push_back(mark[v]);
            }
        }
    }
}

bool dfs(int u) {
    for (int i = 0; i < G2[u].size(); i++) {
        int v = G2[u][i];
        if (!check[v]) {
            check[v] = true;
            if (matching[v] == -1 || dfs(matching[v])) {
                matching[v] = u;
                return true;
            }
        }
    }
    return false;
}

void solve() {
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) tarjan(i);
    }

    memset(pre, 0, sizeof(pre));
    rebuild();

    int max_match = 0;
    memset(matching, -1, sizeof(matching));
    for (int i = 1; i <= scc_cnt; i++) {
        if (matching[i] == -1) {
            memset(check, 0, sizeof(check));
            if (dfs(i)) max_match++;
        }
    }

    printf("%d\n", scc_cnt - max_match);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        init();
        solve();
    }
}

拆点

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

using namespace std;

const int MAX = 5000 + 10;

vector<int> G1[MAX], G2[2 * MAX];

int n, m, T;

int pre[MAX], low[MAX], mark[MAX], dfs_clock, scc_cnt;
stack<int> S;

int check[2 * MAX], matching[2 * MAX];

void tarjan(int u) {
    low[u] = pre[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G1[u].size(); i++) {
        int v = G1[u][i];
        if (!pre[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        if (!mark[v]) {
            low[u] = min(low[u], pre[v]);
        }
    }
    if (low[u] == pre[u]) {
        ++scc_cnt;
        int x;
        do {
            x = S.top();
            S.pop();
            mark[x] = scc_cnt;
        } while (x != u);
    }
}

void init() {
    memset(pre, 0, sizeof(pre));
    memset(mark, 0, sizeof(mark));
    scc_cnt = dfs_clock = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) G1[i].clear();
    for (int i = 1; i <= 2 * n; i++) G2[i].clear();
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G1[u].push_back(v);
    }
}

void rebuild() {
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < G1[u].size(); i++) {
            int v = G1[u][i];
            if (mark[u] != mark[v]) {
                G2[mark[u]].push_back(mark[v] + scc_cnt);
            }
        }
    }
}

bool dfs(int u) {
    for (int i = 0; i < G2[u].size(); i++) {
        int v = G2[u][i];
        if (!check[v]) {
            check[v] = true;
            if (matching[v] == -1 || dfs(matching[v])) {
                matching[v] = u;
                matching[u] = v;
                return true;
            }
        }
    }
    return false;
}

void solve() {
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) tarjan(i);
    }

    memset(pre, 0, sizeof(pre));
    rebuild();

    int max_match = 0;
    memset(matching, -1, sizeof(matching));
    for (int i = 1; i <= 2 * scc_cnt; i++) {
        if (matching[i] == -1) {
            memset(check, 0, sizeof(check));
            if (dfs(i)) max_match++;
        }
    }

    printf("%d\n", scc_cnt - max_match);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        init();
        solve();
    }
}
ACM►图论►连通性

HDU1827 - Summer Holiday(强连通+缩点)

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1827

题目大意：

给出一个有向图，选择若干的点作为起点，使得从这些起点出发可以遍历所有的点，选出每个点为起点需要花费$A_i$，求最小费用。
$N <= 1000, M <= 2000$

解题过程：

想起来还是比较容易的，因为在刷强连通的题，想到缩点转化成DAG就简单了。
不过卡了好久，因为自己的++dfs_clock写成dfs_clock++了。

题目分析：

首先进行强连通分量分解，缩点化为DAG，因为强连通的每个点都可以互相到达，那么只需要能到达强连通分量里面的任一点就可以了，对于缩点后，他的费用为他包含的所有点中最小的。

然后现在是一个DAG图，如果一个点的入度不为0，那么他一定可以从另外的一个点到达，那么我只需要选取所有入度为0的点，并累加他们的值既可以了。

AC代码：

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;

const int MAX = 1000+10;
const int INF = 0x3f3f3f3f;

int n, m;

//G1为原图，G2为重建的图
vector<int> G1[MAX], G2[MAX];
//原始费用，重建的图的费用
int cost[MAX], ans_cost[MAX];

int low[MAX], dfn[MAX], mark[MAX], scc_cnt, dfs_clock;
int in[MAX], out[MAX];
stack<int> S;

void tarjan(int u) {
    low[u] = dfn[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G1[u].size(); i++) {
        int v = G1[u][i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (!mark[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        int x;
        ++scc_cnt;
        do {
            x = S.top();
            S.pop();
            mark[x] = scc_cnt;
        } while (x != u);
    }
}

void rebuild() {
    //枚举每条边进行重建图
    for (int u = 1; u <= n; u++) {
        //更新强连通分量的花费
        ans_cost[mark[u]] = min(ans_cost[mark[u]], cost[u]);
        for (int i = 0; i < G1[u].size(); i++) {
            int v = G1[u][i];
            if (mark[u] != mark[v]) {
                in[mark[v]]++;
                G2[mark[u]].push_back(mark[v]);
            }
        }
    }
}

void init() {
    memset(dfn, 0, sizeof(dfn));
    memset(ans_cost, INF, sizeof(ans_cost));
    memset(mark, 0, sizeof(mark));
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    scc_cnt = dfs_clock = 0;
    for (int i = 1; i <= n; i++) {
        G1[i].clear(); G2[i].clear();
        scanf("%d", cost + i);
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G1[u].push_back(v);
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    rebuild();

    int ans = 0, ans_cnt = 0;
    //统计入度为0的点
    for (int i = 1; i <= scc_cnt; i++) {
        if (in[i] == 0) ans += ans_cost[i], ans_cnt++;
    }
    printf("%d %d\n", ans_cnt, ans);
}

int main() {

    while (~scanf("%d %d", &n, &m)) {
        init();
        solve();
    }
}