aytony

求古寻论，散虑逍遥。

0%

题解 [USACO13OPEN]Photo G

发表于 更新于 分类于 ，
题解 [USACO13OPEN]Photo G

P3084 [USACO13OPEN]Photo G - 洛谷 计算机科学教育新生态

题目大意

对于一个 01 序列 \(a_1, \cdots a_n\) , 给出 \(m\) 个区间，保证每个区间里有且仅有一个 1 。求序列里最多有多少个 1 。

其中 \(1 \leqslant n \leqslant 200000\) , \(1 \leqslant m \leqslant 100000\) 。

算法选择

可以选择动态规划，也可以选择差分约束。在这里选择最短路差分约束作为练习。

算法 差分约束 | 散虑の春雨寻风

具体思路

设 \(S_n\) 为序列前 \(n\) 项的和，则对于此 01 序列本身 \(S_{i-1} \leqslant S_i \leqslant S_{i-1}+1\) 的性质可以列出方程

\[    \left\{        \begin{aligned}            &S_{i-1} - S_i \leqslant 0 \\            &S_i - S_{i-1} \leqslant 1 \quad (i = 1, 2, \cdots , n)        \end{aligned}    \right.    \]

同时由给出的 \(m\) 个条件列出方程

\[    \left\{        \begin{aligned}            &S_{b_i} - S_{a_i-1} \leqslant 1 \\            &S_{a_i-1} - S_{b_i} \leqslant -1 \quad (i = 1, 2, \cdots , m)        \end{aligned}    \right.    \]

之后连图跑 SPFA 判负环，计算即可， \(S_n\) 即为所求。

代码实现

  • 裸 SPFA 算法只能打出 70pts 。
  • SPFA 算法使用 swap-SLF 优化：每次队列改变后检查队首队尾，若是存在 dis[que.front()] > dis[que.end()] 便交换队列首尾。优化后可以拿到 90pts。
  • 加入时间检测判负环，即若是时间到达 0.95s 仍进行 SPFA 循环，便直接判断负环存在并跳出。优化后可以 AC 。（clock() 返回程序运行时间，以 clock 为单位。在编译器中，1s 时间对应的 clock 数由宏 CLOCKS_PER_SEC 定义，不同系统中不同。）
  • 实际上，时间检测判负环的结果有一定的错误率，因为实际上算法并没有跑完便中断了。只是我们认为在 1s 的时间内跑不完 SPFA 的数据大概率是存在负环的。

时间复杂度 \(O(KN)\) , 用时 1.40s 。

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 <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <ctime>

using namespace std;

const int NMAX = 200005;
const int MMAX = 600005;
const int INF = 0x7f7f7f7f;

struct edge
{
    int from, to, w;
    edge *nxt;
};

// 全局
int n, m;
// 图
edge edges[MMAX], *head[NMAX];
int cnt;
// SPFA
int dis[NMAX];
// 计时
clock_t lim = 0.95 * CLOCKS_PER_SEC;

bool SPFA(int begin)
{
    bool inq[NMAX];
    int vis[NMAX];
    deque<int> que;
    memset(dis, INF, sizeof(dis));
    memset(inq, 0, sizeof(inq));
    memset(vis, 0, sizeof(vis));

    dis[begin] = 0;
    que.push_back(begin), inq[begin] = true, vis[begin]++;
    while (!que.empty())
    {
        int fnt = que.front();
        que.pop_front(), inq[fnt] = false;
        if (dis[que.front()] > dis[que.back()]) // swap-SLF
            swap(que.front(), que.back());
        for (register edge *i = head[fnt]; i; i = i->nxt)
            if (dis[i->to] > dis[fnt] + i->w)
            {
                dis[i->to] = dis[fnt] + i->w;
                if (!inq[i->to])
                {
                    que.push_back(i->to), inq[i->to] = true, vis[i->to]++;
                    if (dis[que.front()] > dis[que.back()]) // swap-SLF
                        swap(que.front(), que.back());
                    if (vis[i->to] >= n)
                        return false;
                }
            }
        if (clock() >= lim) // 计时
            return false;
    }
    return true;
}

inline void addline(int from, int to, int w)
{
    edges[cnt] = (edge){from, to, w, head[from]};
    head[from] = &edges[cnt++];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (register int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        u--;
        addline(u, v, 1);
        addline(v, u, -1);
    }
    for (register int i = 0; i < n; i++)
    {
        addline(i + 1, i, 0);
        addline(i, i + 1, 1);
    }

    if (!SPFA(0))
        puts("-1");
    else
        printf("%d\n", dis[n]);

    system("pause");
    return 0;
}

2020-08-08 Update: 更正了关于 clock() 函数的解释。