23-9-19-模拟赛题解

文章发布时间:

最后更新时间:

文章总字数:
890

预计阅读时间:
4 分钟

9/19模拟赛题解

T1. SYOJ #532 / Luogu P2294

区间和速算比赛 / 狡猾的商人

【大体思路】

　　差分约束（Spfa）+ 前缀和

【详解】

　　经典差分约束模板题。要判有无解，其实就是按照差分约束规则建个图，判断图上有无环，如果有环则无解。

　　在这里写一下差分约束基本规则方便复习：

  • 　　如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成 “” 的形式，建图后求最短路；
  • 　　如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成 “” 的形式，建图后求最长路。

　　假设我们现在要求最小值，需要跑最长路，那么现在应该这样建边：

  1. 如果 ，则 ，

  2. 如果 ，则

  3. 如果 ，则

  4. 如果 ，则

  5. 如果 ，则

　　对于常见需要使用差分约束的问题经常会用到超级源点的思想，没有起点的时候不要忘记用这点小东西。

【代码】

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 2e4 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int t, n, m, flag;
int dist[N], vis[N], cnt[N];
int head[N], edge[M * 2], nxt[M * 2], w[M * 2], tot;
void add(int x, int y, int z) {
    edge[++tot] = y;
    nxt[tot] = head[x];
    w[tot] = z;
    head[x] = tot;
}
void spfa(int s) {
    queue<int>q;
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    q.push(s);
    while (q.size()) {
        int x = q.front();
        q.pop();
        cnt[x]++;
        if (cnt[x] > n) {
            flag = 1;
            return ;
        }
        vis[x] = 0;
        for (int i = head[x]; ~i; i = nxt[i]) {
            int y = edge[i], z = w[i];
            if (dist[y] > dist[x] + z) {
                dist[y] = dist[x] + z;
                if (!vis[y]) {
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}
int main() {
    scanf("%d", &t);
    while (t--) {
        memset(head, -1, sizeof(head));
        tot = 0;
        flag = 0;
        scanf("%d%d", &n, &m);
        while (m--) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add(x - 1, y, z);
            add(y, x - 1, -z);
        }
        for (int i = 1; i <= n; i++) {
            add(n + 1, i, 0);
        }
        spfa(n + 1);
        if (!flag) {
            puts("AC");
        } else {
            puts("WA");
        }
    }
    return 0;
}

T2. SYOJ #644 / Luogu P1197

网络破坏 / 星球大战

【大体思路】

　　逆向思维 + 并查集

【详解】

　　发现好像没见过删点的题，但是删点反过来不就成了建点嘛。然后就是非常基础的思路了，总之就是把题目的操作顺序全倒过来，由最终的散乱状态连接回起始一整块的状态，再把询问倒着输出就完成了。

【代码】

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<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 4e5 + 5;
int n, m, k, tot, fa[N], lis[N];
int head[N], edge[N], from[N], nxt[N], ans[N];
bool vis[N];
void add(int x, int y) {
    edge[++tot] = y;
    from[tot] = x;
    nxt[tot] = head[x];
    head[x] = tot;
}
int fd(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = fd(fa[x]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    scanf("%d", &k);
    tot = n - k ;
    for (int i = 1; i <= k; i++) {
        int x;
        scanf("%d", &x);
        vis[x] = 1;
        lis[i] = x;
    }
    for (int i = 1; i <= m * 2; i++) {
        int x = from[i], y = edge[i];
        if (!vis[x] && !vis[y] && fa[fd(x)] != fa[fd(y)]) {
            fa[fd(x)] = fa[fd(y)];
            tot--;
        }
    }
    ans[k + 1] = tot;
    for (int i = k; i >= 1; i--) {
        int x = lis[i];
        tot++;
        vis[x] = 0;
        for (int j = head[x]; j; j = nxt[j]) {
            int y = edge[j];
            if (!vis[y] && fa[fd(x)] != fa[fd(y)]) {
                fa[fd(x)] = fa[fd(y)];
                tot--;
            }
        }
        ans[i] = tot;
    }
    for (int i = 1; i <= k + 1; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}
≡