ACM►知识小结

常见错误清单（长期更新）

  • 素数筛打表的时候默认为1为素数

  • DP转移过程中记录路径的情况，如果是从后向前算的，可能路径会被更新掉

  • 每组数据初始化的时候，注意把建的边清掉一下

  • 对一堆数字进行取LCM的时候，可能会爆int

  • 结构体注意初始化问题，不要以为默认会被初始化为0，最好手写构造函数

  • ～是按位取反，只需要把一位取反的时候不要用

  • 线段树区间更新时updata忘记加lazy标记

  • 输出结果的时候，有时直接输出结构体本地不会错，交上RE，注意下要输出结构体的属性

  • 容斥原理判断某范围内模一些数为0的数的个数的时候，要求这些数之间不能一个数是另一个的倍数，比如2, 3, 4, 5，那么应该舍弃掉4，只取2

  • SPFA用栈替换成队列后，要注意出栈的顺序，要在加入新元素前把旧的出栈，加入新元素后取消出栈元素的标记

  • BFS某些情况应该在入队的时候标记，如果在出队的时候标记，有可能会出现一些不可描述的情况导致MLE

  • 数据太大爆int

  • 计算过程中爆int

  • 取模姿势不对爆int

  • vis，book等标记数组没初始化

  • bfs队列没有pop

  • 类似走迷宫那样的题，下一步要走的地方计算错误(比如ty 本应该是y+dirc[i][0]，结果写成x+dirc[i][0])

  • 浮点数精度误差，要加eps

  • 数组过大每次都要memset初始化，导致超时

  • Case： 和数组之间有个空格，导致pe

  • 直接拿输入的数据当下标，因为有负数re

  • DP过程累加爆int

  • 题目卡SPFA换Dijstra AC

  • 题目卡Vector，用前向星AC

  • DP输出路径时，尽量要从末状态从后往前推，这样容易处理字典序

  • 解方程中，可能爆 int ，比如二元一次方程中的 B 来自输入的两个数据相乘，然后又用到了 B * B 结果 1000 的数据就会爆 int

  • 位运算一定要括起来，某些位运算操作优先级比等于号还低

  • 计算一组数据需要取膜时，记得手动初始化的也要取膜，比如斐波那契数列，f(1) = f(0) = 1 时， 如果模数为 1 那么应该初始化为 0 才对，保险写法为 f(1) = f(0) = 1 % mod

  • 代码WA的时候要多检查下比较长的公式是否错误

  • 对于 long long a = b b b 这样的式子要注意 b 是否为 long long 类型，如果不是运算过程中为 int 类型，检查下是否爆 int

  • 注意数据范围， 2^31 是爆 int 的

  • 用矩阵存图的时候，注意重边，如果有重边看情况更新

ACM►图论►网络流

POJ2135 - Farm Tour（最小费用流 + 模板 + SPFA + Dijstra）

题目链接：

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

题目大意：

现在有 N 个节点，有M条边，要从 1 走到 N 然后再回到 1 。要求走的边不能重复，求最短路径。

解题过程：

之前看了最小费用最大流然后一直没有做题，于是找了一个模板题来刷，对着板子敲上去居然一次AC，然后又改了下最短路的算法，AC。

题目分析：

算是一个隐含的最小费用最大流，设每条边的容量为1，花费为路径长度。那么所求的就是一个从起点 1 到终点 N 流量为 2 的流的最小费用流。

这里用的是最短增广路算法。

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
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 1123, INF = 0x3f3f3f3f;
int N, M;

struct Node{
    int to, cap, cost, rev;
    Node(int to, int cap, int cost, int rev):to(to), cap(cap), cost(cost), rev(rev){}
};

vector<Node> edge[MAX];
int dist[MAX], vis[MAX], prevv[MAX], preve[MAX];

void add_edge(int from, int to, int cap, int cost) {
    edge[from].push_back(Node(to, cap, cost, edge[to].size()));
    edge[to].push_back(Node(from, 0, -cost, edge[from].size()-1));
}

int min_cost_flow(int s, int t, int f) {
    int rst = 0;
    //循环到到达了f流量
    while (f > 0) {
        memset(dist, INF, sizeof(dist));
        queue<int> q;
        q.push(s);
        vis[s] = 1;
        dist[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            for (int i = 0; i < edge[u].size(); i++) {
                Node& e = edge[u][i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    prevv[e.to] = u;
                    preve[e.to] = i;
                    if (!vis[e.to]) {
                        q.push(e.to);
                        vis[e.to] = 1;
                    }
                }
            }
            q.pop();
            vis[u] = 0;
        }
        if (dist[t] == INF) return -1;

        //最路径上最小流量
        int d = f;
        for (int u = t; u != s; u = prevv[u]) {
            d = min(d, edge[prevv[u]][preve[u]].cap);
        }
        //剩余的流量
        f -= d;
        //计算费用
        rst += d * dist[t];
        //修改路上所经过的边的容量
        for (int u = t; u != s; u = prevv[u]) {
            Node& e = edge[prevv[u]][preve[u]];
            e.cap -= d;
            edge[u][e.rev].cap += d;
        }
    }
    return rst;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        add_edge(from, to, 1, cost);
        add_edge(to, from, 1, cost);
    }
    //求流量为2的最小费用
    int ans = min_cost_flow(1, N, 2);
    printf("%d\n", ans);
}

#居然可以AC的Dijstra代码：

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
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 1123, INF = 0x3f3f3f3f;
int N, M;

struct Node{
    int to, cap, cost, rev;
    Node(int to, int cap, int cost, int rev):to(to), cap(cap), cost(cost), rev(rev){}
};

vector<Node> edge[MAX];
int dist[MAX], vis[MAX], prevv[MAX], preve[MAX];

void add_edge(int from, int to, int cap, int cost) {
    edge[from].push_back(Node(to, cap, cost, edge[to].size()));
    edge[to].push_back(Node(from, 0, -cost, edge[from].size()-1));
}

int min_cost_flow(int s, int t, int f) {
    int rst = 0;
    while (f > 0) {
        memset(dist, INF, sizeof(dist));
        queue<int> q;
        q.push(s);
        vis[s] = 1;
        dist[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            for (int i = 0; i < edge[u].size(); i++) {
                Node& e = edge[u][i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    prevv[e.to] = u;
                    preve[e.to] = i;
                    if (!vis[e.to]) {
                        q.push(e.to);
                        vis[e.to] = 1;
                    }
                }
            }
            q.pop();
            vis[u] = 0;
        }
        if (dist[t] == INF) return -1;

        int d = f;
        for (int u = t; u != s; u = prevv[u]) {
            d = min(d, edge[prevv[u]][preve[u]].cap);
        }
        f -= d;
        rst += d * dist[t];
        for (int u = t; u != s; u = prevv[u]) {
            Node& e = edge[prevv[u]][preve[u]];
            e.cap -= d;
            edge[u][e.rev].cap += d;
        }
    }
    return rst;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        add_edge(from, to, 1, cost);
        add_edge(to, from, 1, cost);
    }
    int ans = min_cost_flow(1, N, 2);
    printf("%d\n", ans);
}

ACM►图论►最短路

HDU4725 - The Shortest Path in Nya Graph （Dijstra + 建图）

题目链接：

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

题目大意：

现在有N个节点，编号从1到N。有M条权值为Ci无向边，链接着两个节点。
新加入了一个条件，每个节点在一个层内，假设在 x 层，那么在 x 层内的节点可以直接到达 x + 1 层或 x -1 层的任意节点，花费为 C 。

现在求从 1 到 N 的最短路。

解题过程：

比赛的时候没做出来，现在才开始补题，当时觉得挺难的，没想到拆点重新建图。想通了就觉得挺简单了，然后处理下细节，不过这个题卡 SPFA 有点坑。

题目分析：

对于每一层，加入两个点，一个入点，一个出点。入点和出点和这一层里的所有点连一条边，并且权值为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
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 312345, INF = 0x3f3f3f3f;

int N, M, C;

vector<pair<int, int> > edge[MAX];
int vis[MAX], dist[MAX];

int dijstra() {
    //普通的dijstra求最短路
    memset(dist, INF, sizeof(dist));
    priority_queue<pair<int, int> > q;
    q.push(make_pair(0, 1));
    dist[1] = 0;
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        for (int i = 0; i < edge[u].size(); i++) {
            int v = edge[u][i].first;
            int w = edge[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push(make_pair(-dist[v], v));
            }
        }
    }
    return dist[N];
}

int main() {
    int T, cases = 0;
    scanf("%d", &T);
    while (T--) {

        for (int i = 0; i <= N*3; i++) {
            edge[i].clear();
            vis[i] = 0;
        }

        scanf("%d %d %d", &N, &M, &C);
        for (int i = 1; i <= N; i++) {
            int t;
            scanf("%d", &t);
            vis[t] = 1;
            //这里 t*2-1+N 代表第 t 层的入点， t*2+N 代表出点
            edge[t*2-1+N].push_back(make_pair(i, 0));
            edge[i].push_back(make_pair(t*2+N, 0));
        }

        for (int i = 0; i < M; i++) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            edge[u].push_back(make_pair(v, w));
            edge[v].push_back(make_pair(u, w));
        }

        for (int i = 1; i <= N; i++) {
            int u = N + i*2;

            //当前层的出点与相邻层的入点建边
            if (i > 1) {
                int v = u-3;
                edge[u].push_back(make_pair(v, C));
            }
            if (i < N) {
                int v = u+1;
                edge[u].push_back(make_pair(v, C));
            }
        }

        int ans = dijstra();
        printf("Case #%d: %d\n", ++cases, ans == INF? -1:ans);
    }
}
ACM►DP

HDU5550 - Game room （DP）

题目链接：

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

题目大意：

有一栋楼，有N层，每一层都有ai个想要玩A游戏的，bi个想要玩B游戏的，但是每层只能修建一种游戏厅。每个人移动上下一层楼需要消耗一点体力。使得所有人玩的上游戏并且消耗的体力尽量的少，最少消耗的体力。

解题过程：

比赛的时候好不容易读懂了题意，发现并不会做，第一个想法是贪心的，从0层向下扫，累加想玩A游戏的人数和想玩B游戏的人数，对于每一层判断是想玩A的人多还是想玩B的人多，修建人多的那个。

显然这个思路得不到最优解，如果每个人只能向下走不能向上走的话应该可行。

然后这个题放置了好长时间，现在才去补，翻了两三个博客算是看懂了，感觉这种DP只能靠脑洞了，每一种都不一样。

参考博客：
https://ramay7.github.io/2016/11/04/HDU-5550-2015CCPC-K-dp/

http://blog.csdn.net/snowy_smile/article/details/49618219

题目分析：

上面两个博客都说的非常详细，我主要是参照是第一个博客，代码加了注释，这里不做过多论述了。

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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 4010;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

int T, n, cases = 0;
ll value[MAX_N][2], sum[MAX_N][2], pre[MAX_N][2], suf[MAX_N][2];
ll dp[MAX_N][2];

void init() {
    //初始化求出前缀和，pre[i]表示从第i层移到第0层所需要的代价，suf[i]代表从第i层移到第n+1层所需要的代价
    for (int i = 1; i <= n; i++) {
        sum[i][0] = sum[i-1][0] + value[i][0];
        sum[i][1] = sum[i-1][1] + value[i][1];
        pre[i][0] = pre[i-1][0] + value[i][0] * i;
        pre[i][1] = pre[i-1][1] + value[i][1] * i;
    }
    for (int i = n; i >= 1; i--) {
        suf[i][0] = suf[i+1][0] + value[i][0] * (n - i + 1);
        suf[i][1] = suf[i+1][1] + value[i][1] * (n - i + 1);
    }
}

ll down(int a, int b, int id) {
    //表示 [a, b] 这个区间里的人要达到b+1所需要的代价
    return suf[a][id] - suf[b+1][id] - (sum[b][id] - sum[a-1][id]) * (n-b);
}

ll up(int a, int b, int id) {
    //表示 [a,b] 这个区间里的人要到达a所需要的代价
    return pre[b][id] - pre[a][id] - (sum[b][id] - sum[a][id]) * a;
}

ll work(int a, int b, int id) {
    int mid = (a+b) >> 1;
    //因为dp[i][0]表示的状态是当前是0，i+1是1，如果当前i为n，那么后面就没有1的房间了
    if (b < n) return up(a, mid, id) + down(mid+1, b, id);
    else return up(a, b, id);
}

void solve() {
    init();
    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i][1] = INF;
        //计算前i个全为1或全为0的情况
        if (i < n) dp[i][0] = down(1, i, 1);
        if (i < n) dp[i][1] = down(1, i, 0);
        for (int j = 1; j <= i-1; j++) {
            //枚举上一个选1或0的位置
            dp[i][0] = min(dp[i][0], dp[j][1] + work(j, i, 1));
            dp[i][1] = min(dp[i][1], dp[j][0] + work(j, i, 0));
        }
    }
    printf("Case #%d: %lld\n", ++cases, min(dp[n][0], dp[n][1]));
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld", &value[i][0], &value[i][1]);
        }
        solve();
    }
}
ACM►图论►网络流

HDUOJ3549 - Flow Problem（网络流+最大流最小割+模板）

题目链接：

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

题目大意：

有向图求最大流

解题过程：

关于为什么增加流量时要增加一个反向负流量的边纠结了很久，最后还是想通了，其他就没难点了。

题目分析：

增广路算法，每一次尽可能的添加一条增广路，直到不能添加增广路为止，不过有个特殊的地方，按照挑战书上的说法是，可以把之前的流推回去。按照我的理解大概是现在的这个新加的增广路用之前流量的路径，然后把之前流的路径推回去，然后之前的流量寻找一个新的路径。

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

const int MAX = 20, INF = 0x3f3f3f3f;

struct Node {
    //to表示要指向的点，cap是剩余流量，rev是指这条边的方向边是to这个点的第几条边
    int to, rev, cap;
    Node(int to, int cap, int rev):to(to), cap(cap), rev(rev) {}
};

vector<Node> edge[MAX];
int vis[MAX];

void add_edge(int u, int v, int w) {
    //添加边和反向边
    edge[u].push_back(Node(v, w, edge[v].size()));
    edge[v].push_back(Node(u, 0, edge[u].size()-1));
}

int dfs(int u, int end, int f) {
    if (u == end)
        return f;
    vis[u] = 1;
    for (int i = 0; i < edge[u].size(); i++) {
        Node& e = edge[u][i];
        if (!vis[e.to] && e.cap > 0) {
            int d = dfs(e.to, end, min(f, e.cap));
            //如果找到了增广路就返回
            if (d > 0) {
                //正向边容量减少的时候，反向边要增加容量
                e.cap -= d;
                edge[e.to][e.rev].cap += d;
                return  d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0;
    for (;;) {
        memset(vis, 0, sizeof(vis));
        int f = dfs(s, t, INF);
        //如果找不到增广路了，那么当前就是最大流了，返回
        if (f == 0)
            return flow;
        flow += f;
    }
}

int main() {
    int T;
    scanf("%d", &T);
    for (int cases = 1; cases <= T; cases++) {
        int n, m;
        scanf("%d %d", &n, &m);

        for (int i = 0; i <= n; i++)
            edge[i].clear();

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

        printf("Case %d: %d\n", cases, max_flow(1, n));
    }
}
ACM►DP►状压DP

POJ2411 - Mondriaan's Dream （状压DP+轮廓线DP）

题目链接：

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

题目大意：

这题题意非常明确，现在有一个 M × N 的矩形，你现在有很多个 2 × 1 大小的方块，现在要用这些方块铺满这个矩形，请问有多少种铺法。

解题过程：

这题不是遇到卡住的，是学新知识的模板题，然后顺着书的思路做的，理解还是花了一番功夫。先看的挑战那本书，后来又翻了下大白书，还是 LRJ 的书写的详细易读，最后终于看懂了。

刚开始理解错状态了，书上专门说了下多段图路径问题，然后我顺便把状态理解成每一行的对应 2 ^ M 个状态了，然后状态转移的时候怎么想都不对，最后又看了下复杂度，才发现是 O ( N × M × 2 ^ M )，然后看了下完整代码，发现每一行的每一列都是一个阶段，每个阶段对应 2 ^ M 个状态，然后一个新状态由上一个阶段的状态转移而来。

题目分析：

首先确定状态。

假设我是从左上角开始依次从左至右从上至下的放方块，那么可以得出结论：假设现在要放的点为 (i, j)，大小按照字典序（先按行，后按列）。 那么对于所有的点 (i’, j’) >= (i, j) 一定是还没有放。对于所有 (i’, j’) < (i-1, j) 的点一定是已经放了方块的。

这里写图片描述

假设我要放置 (4, 4) 这个点，那么绿色的地方都是已经铺满的，蓝色的地方都是未铺的，黄色的地方是未确定的。接下来只要状态压缩表示黄色的部分好了。用 1 表示已铺，0 表示未铺。

这里写图片描述

然后放置一个位置 (i, j)的时候有三种方式，分别是不放，向上竖着放，向左横着放。如果是不放，那么 (i-1, j) 位置一定是已经铺了的，否则不可能转移到一个合法的状态。如果是向上竖着放，那么 (i-1, j) 一定要是未铺的。如果向左横着放，那么 (i, j-1) 一定是未铺的。

这里写图片描述

此外大白书上介绍了多段图的概念。有 n 列节点，每列称一个阶段，每个阶段的节点只会先下一个阶段的节点连有向边。本题就可以转化为从多段图的一个节点到达另一个节点的路径个数，矩形里的每一个方块都是一个阶段。而且递推的时候要求一个阶段只需要用到他的上一个阶段，所以可以用滚动数组实现。

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
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;

const int MAX = 15;
int n, m, cur;
ll dp[2][1<<MAX];

int main() {
    while (~scanf("%d %d", &n, &m) && (n+m)) {
        if (n < m) swap(n, m);
        memset(dp, 0, sizeof(dp));
        cur = 0;
        //初始化状态，看做第一行的上一行已经全部铺满
        dp[cur][(1<<m)-1] = 1;

        //枚举每一行每一列
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j++) {
                //滚动数组
                cur ^= 1;
                memset(dp[cur], 0, sizeof(dp[cur]));
                for (int k = 0; k < (1<<m); k++) {
                    ll num = dp[cur^1][k];
                    //判断要放的位置的上面一块是否已铺
                    if (k&(1<<(m-1))) {
                        //不放
                        dp[cur][(k<<1)^(1<<m)] += num;
                        //判断要放的位置的左边一块是否未铺
                        if (j && !(k&1)) {
                            //向左横着放
                            dp[cur][((k<<1)^(1<<m))+3] += num;
                        }
                    }
                    else if (i) {
                        //向上竖着放
                        dp[cur][(k<<1)+1] += num;
                    }
                }
            }
        }
        printf("%lld\n", dp[cur][(1<<m)-1]);
    }
}
ACM►图论►差分约束

POJ3169 - Layout （差分约束）

题目链接：

https://cn.vjudge.net/problem/POJ-3169

题目大意：

这里写图片描述

解题过程：

刚开始是一脸懵逼的，怎么还有这种题，完全没想法。
然后看书上说是差分约束，然后和最短路类比了下，还是没看懂，最后是去网上搜了下博客，然后又自己画了画才弄懂。

http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

题目分析：

关于最短路，设函数 d(v) 的含义是从起点到节点 v 的最短距离，那么对于任意权值为 w 的边 e = (u, v) ，都有 d(u) + w >= d(v) 成立，公式可化为 w >= d(v) - d(u) 。最短路就是求解这组方程，变量是 d(v/x) ，求解这组方程就是意味着求出满足方程的 d(v) - d(u) 的最大值。

对于这个题目，有三个约束条件，第一个是牛按编号顺序排，第二个是某两头牛之间的距离不能大于一个值，第三个是某两头牛之间的距离必须不小于一个值。

假设这两头牛分别是 u 和 v ，(v > u)，约束距离是 w ，对于第一个条件， d(v) - d(u) >= 0 即 d(v) + 0 >= d(u) ，从v向u建一条权值为 0 的边。

对于第二个条件，d(u) + w >= d(v)，即从 u 向 v 建一条权值为 w 的边。

对于第三个条件，d(u) + w <= d(v)， d(v) - w >= d(u)，从 v 向 u 建一条权值为 -w 的边。

然后对于上面所建立的图，求出从起点到节点的最短距离即是答案。

如果这个图无法联通，表示没有可行的方案。如果存在负环，那么这个距离是可以无限大的。

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
#include <vector>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;

const int MAX = 11234, INF = 0x3f3f3f3f;
int frequency[MAX], dist[MAX], vis[MAX];
int N, ML, MD;
vector<pair<int, int> > edge[MAX];

int spfa() {
    memset(dist, INF, sizeof(dist));
    queue<int> q;
    q.push(1);
    dist[1] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;

        for (int i = 0; i < edge[u].size(); i++) {
            int v = edge[u][i].first;
            int w = edge[u][i].second;

            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!vis[v]) {
                    vis[v] = 1;
                    frequency[v]++;
                    if (frequency[v] > N)
                        return -INF;
                    q.push(v);
                }
            }
        }
    }

    return dist[N];
}

int main() {
    scanf("%d %d %d", &N, &ML, &MD);

    int u, v, w;
    for (int i = 2; i <= N; i++) {
        edge[i].push_back(make_pair(i-1, 0));
    }
    for (int i = 0; i < ML; i++) {
        scanf("%d %d %d", &u, &v, &w);
        edge[u].push_back(make_pair(v, w));
    }
    for (int i = 0; i < MD; i++) {
        scanf("%d %d %d", &u, &v, &w);
        edge[v].push_back(make_pair(u, -w));
    }

    int ans = spfa();
    if (ans <= -INF) {
        printf("-1\n");
    }
    else if (ans >= INF) {
        printf("-2\n");
    }
    else {
        printf("%d\n", ans);
    }
}
ACM►数据结构►并查集

POJ1182 - 食物链（带权并查集）

题目链接：

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

题目大意：

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

解题过程：

这题主要是看的书和博客，之前没接触过带权并查集。

题目分析：

这题用两种做法做了下，一种是挑战程序设计竞赛中的，另一种是搜的博客上面的。

首先说下简单粗暴的第一种方法：

一：

这里写图片描述

二：

对于每个节点有一个 Rank数组表示权值，这里引用两个blog好了：
http://blog.csdn.net/qq_24451605/article/details/46876121
http://blog.csdn.net/c0de4fun/article/details/7318642/

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
#include<cstdio>
using namespace std;

const int MAX = 1123456;

int N, K;

int f[MAX];

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

int connect(int a, int b) {
    int fa = root(a);
    int fb = root(b);
    f[fa] = fb;
}

int same(int a, int b) {
    return root(a) == root(b);
}

void init() {
    for (int i = 0; i <= N*3; i++)
        f[i] = i;
}


int main() {
    int ans = 0;
    scanf("%d %d", &N, &K);
    init();
    for (int i = 0; i < K; i++) {
        int D, X, Y;
        scanf("%d %d %d", &D, &X, &Y);
        if (X > N || X < 1 || Y < 1 || Y > N) {
            ans++;
            continue;
        }
        else if (D == 1) {
            if (same(X, Y+N) || same(X, Y+N*2)) {
                ans++;
                continue;
            }
            connect(X, Y);
            connect(X+N, Y+N);
            connect(X+N*2, Y+N*2);
        }
        else {
            if (same(X, Y) || same(X, Y+N*2)) {
                ans++;
                continue;
            }
            connect(X, Y+N);
            connect(X+N, Y+N*2);
            connect(X+N*2, Y);
        }
    }
    printf("%d\n", ans);
}

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
#include<cstdio>
using namespace std;

const int MAX = 112345;

int ran[MAX], f[MAX];
int N, K;


void init() {
    for (int i = 0; i <= N; i++)
        f[i] = i, ran[i] = 0;
}

int root(int x) {
    if (x == f[x])
        return x;
    int temp = f[x];
    f[x] = root(f[x]);
    ran[x] = (ran[x] + ran[temp])%3;
    return f[x];
}

void connect(int a, int b, int type) {
    int fa = root(a);
    int fb = root(b);
    if (fa == fb)
        return;
    f[fa] = fb;
    ran[fa] = (type+ran[b]-ran[a]+3)%3;
}

bool check(int a, int b, int type) {
    if (a > N || b > N)
        return false;
    if (type == 1 && a == b)
        return false;
    if (root(a) == root(b))
        return (ran[a]-ran[b]+3)%3 == type;
    else
        return true;
}

int main() {
    int ans = 0;
    scanf("%d %d", &N, &K);
    init();
    while (K--) {
        int D, X, Y;
        scanf("%d %d %d", &D, &X, &Y);
        D--;
        if (check(X, Y, D))
            connect(X, Y, D);
        else
            ans++;
    }
    printf("%d\n", ans);
}
ACM►DP►状压DP

ZOJ3777 - Problem Arrangement（状压DP）

题目链接：

https://cn.vjudge.net/problem/ZOJ-3777

题目大意：

现在有一个N×N的矩阵，现在要求在这个矩阵里面取N个来自不同行不同列的数，使这个数大于给定的M。求总共有多少种取法。
(N < 12, M < 500)

解题过程：

组队赛时候的题，当初是暴力DFS的，当作简化的八皇后问题，结果当然是超时。

最近开始补题，正好在刷DP的题，于是顺手切了，算是一个状压DP的模板题。

题目分析：

首先看这个数据量，N和M的范围都非常小，显然可以拿来DP。一个题可以状态压缩，通常有几个量比较小，用来把状态压缩成二进制的数直接储存。

以DP的思路来讲，这题的状态应该是二维的，一个维度是存的状态压缩后的集合，另一个是储存的当前累加的和，DP数组是存的当前解的个数。

首先对于集合S，储存那些行已经有一个数被取了，这样可以保证一个无后效性，并且产生了许多重复子问题。如果前面已经取的点是集合S，并且前面的累加和是M。那么对于后面的数怎么取，有几个解，只需要计算一次即可。下一次如果一个状态仍是取的点的集合是S，并且累加和是M的话，那么直接用上一次计算的结果就可以了。

这样总共的复杂度是O（2^NM）*，即状态总数。

记忆化搜索：

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

#define LL long long

int dp[(1<<13)][600];
int n, m;
int data[112][112];

//计算阶乘
int fun(int n) {
    LL rst = 1;
    for (int i = 1; i <= n; i++) {
        rst *= i;
    }
    return rst;
}

int dfs(int dep, int num, int pre) {

	//递归边界
    if (dep >= n) {
        return num >= m;
    }

    int& ans = dp[pre][num];

    if (ans != -1)
        return dp[pre][num];

    ans = 0;

	//剪枝，如果当前已满足了，那么只需要计算下剩下的组合个数
    if (num >= m)
        return ans = fun(n-dep);

    for (int i = 0; i < n; i++) {
        if (pre&(1<<i))
            continue;
        int temp = pre|(1<<i);
        ans += dfs(dep+1, num+data[dep][i], temp);
    }
    return ans;
}



int main() {

    int T;
    scanf("%d", &T);
    while (T--) {
        memset(dp, -1, sizeof(dp));
        scanf("%d %d", &n, &m);

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

        int aa = fun(n);
        int bb = dfs(0, 0, 0);

        if (bb != 0) {
            int cc = __gcd(aa, bb);
            aa /= cc;
            bb /= cc;
            printf("%d/%d\n", aa, bb);
        }
        else {
            printf("No solution\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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;

int dp[1<<13][666];
int data[112][112];

int fun(int n) {
    int rst = 1;
    for (int i = 2; i <= n; i++)
        rst *= i;
    return rst;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &data[i][j]);
            }
        }
        memset(dp, 0, sizeof(dp));
        
        //代表对于前0行，使和为0的取法有1种
        dp[0][0] = 1;

		
		//遍历每一种取法
        for (int i = 0; i < (1<<n); i++) {
            int cnt = 0;
			
			//计算取到了第几行
            for (int j = 0; j < n; j++) {
                if (i&(1<<j))
                    cnt++;
            }
			
			//尝试取下一个数
            for (int j = 0; j < n; j++) {
                if (i&(1<<j))
                    continue;
				
				//遍历取到的和，如果和大于M，那么加到M那里
                for (int k = 0; k <= m; k++) {
					
					//这里的思想类似背包
                    if (k+data[cnt][j] >= m)
                        dp[i+(1<<j)][m] += dp[i][k];
                    else
                        dp[i+(1<<j)][k+data[cnt][j]] += dp[i][k];
                }
            }
        }
        int ans = dp[(1<<n)-1][m];
        if (ans == 0)
            printf("No solution\n");
        else {
            int aa = fun(n);
            int bb = __gcd(aa, ans);
            printf("%d/%d\n", aa/bb, ans/bb);
        }
    }
}
历程

第八届acm山东省赛总结

比赛过程：

首先看到的是F题，我一开始从后面往前看的，然后队友告诉我F比较简单，然后就去让队友去敲了，我去继续看了其他的题，首先过一遍题是为了找到水题。

不幸的是F题WA了好多次，这时候另一个队友说G是一个水题，好像要算多少次幂的样子，这时就把F打印出来，然后就让队友去敲G了。据说这个题有坑，题目错了，本来是1e9+7的，题面是1e8+7，不过队友好像跳过了这个坑，一次AC。

这时候F题还是一直卡，然后我发现I题挺简单，只是打表找下规律，然后让队友去找了。

然后看了下榜，发现J题A的人非常多，于是跟了下榜，刚开始我想得就是贪心，不过没想到怎么动态的维护最大值，想上二分来着，然后和队友I题找到规律了先去用JAVA大数过了I题。

然后和队友讨论了下找到了J题动态维护最大值的办法。果断敲上去就A掉了。

然后这时候F题还是卡住，这时候只有我还没仔细看过那个题，于是让队友去看别的题了，我去重新敲了一遍，发现是我们理解错题意，然后重新按照正确的理解敲了一边，A掉了。

这时候差不多两个半小时了，最后看了下C题，推出来是二项式定理，然后就开始发午饭了。直接拿着紫书二项式定理的板子敲了下，但是数太大要取模，然后就GG了，只好靠一个会数论的队友了。我最后又用JAVA大数类敲了敲果断超时。

然后最后两个小时，一个队友去看D题，一个看了下A题，最后取模要用到逆元，最终没弄出来，A题博弈最后交了几次也是WA。四题结束。

总结：

感觉还是自己实力太弱，如果队里有两个会数论的话，那么C题应该能做出来了，最后知道A题是经典的博弈，如果自己知识面再广一点的话，也不是一定做不出来，K题好象是贪心加DP，也是可以做的。

以后还是要多训练刷题，提高自己能力……