CFGYM102394A CCPC2019哈尔滨A Artful Paintings

一眼看过去是差分约束板子题，实际上也就是差分约束板子题。

首先这个题可以对答案进行二分。如果铺x个可行，那么x+1个显然可行，所以我们先二分确定一个x。

然后我们的题目转变成了，能不能在恰好铺x个的情况下构造一组合法方案，根据最短路的松弛条件可知，不等式$x_a+v\leq x_b$等价于从a到b，边权为$-v$的边（最短路存在时，令$x_a$表示源点到a的距离，$x_b$同理，那么$x_a$和$x_b$在作为未知变量的时候一定是满足上述不等式的。）

所以我们可以得到，需要建立以下六种不等式：

1. $x_{n-1}+0\leq x_n$(前缀和不减)

2. $x_n+(-1)\leq x_{n-1}$前缀和要么加1要么不变

3. $x_{l-1}+x\leq x_r$ 区间染色数下限

4. $x_r +(x-M) \leq x_{l-1}$ 区间外染色数下限

5. $x_0+M\leq x_n$ 一共至少染M个

6. $x_n+(-M)\leq x_0$ 一共至多染M个(与5一起保证恰好染M个)

然后据此建边，其中$M$是我们二分的铺的个数。建出来的图跑一个从n到0的最短路，如果最短路存在（即没有负环），那说明M可行，答案可以考虑进一步缩小。如果存在负环，则说明M不可行。

但是这里的SPFA要注意优化，大概需要一个SLF（Small Label First），即如果待入队节点的已知最短距离小于队列头部节点，则把他扔到队列头部。

然后别用long long，跑的有点慢。

#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

using int_t = int;

/*
1. x_{n-1}+0<=x_n(前缀和不减)
2. x_n+(-1)<=x_{n-1}前缀和要么加1要么不变
3. x_{l-1}+x<=x_r 区间染色数下限
4. x_r +(x-M) <= x_{l-1} 区间外染色数下限
5. x_0+M<=x_n 一共至少染M个
6. x_n+(-M)<=x_0 一共至多染M个(与5一起保证恰好染M个)

*/

const int_t LARGE = 3010;
const int_t INF = 0x3fffffff;
int_t dis[LARGE + 1];
int_t inqN[LARGE];
bool inqueue[LARGE + 1];
struct Edge {
    int_t to, weight;
    Edge(int_t v, int_t w) : to(v), weight(w) {}
};
struct Limitation {
    int_t left, right, val;
} cond1[LARGE + 1], cond2[LARGE + 1];

int_t n, m1, m2;
//不等式A+X<=B变为边(A,B)，长度-X
std::vector<Edge> graph[LARGE + 1];

void clear() {
    std::fill(dis, dis + 1 + n, INF);
    std::fill(inqueue, inqueue + 1 + n, false);
    std::fill(inqN, inqN + 1 + n, 0);
    for (int_t i = 0; i <= n; i++)
        graph[i].clear();
}

void pushEdge(int_t u, int_t v, int_t w) {
#ifdef DEBUG
    cout << "edge " << u << " to " << v << " val " << w << endl;
#endif
    graph[u].push_back(Edge(v, w));
}
//添加不等式x_a+v<=x_b
void pushLEQ(int_t a, int_t b, int_t v) {
#ifdef DEBUG
    cout << "cond x_" << a << " + " << v << " <= x_" << b << endl;
#endif
    pushEdge(b, a, -v);
}

bool SPFA(int_t src, int_t target) {
    std::deque<int_t> queue;
    dis[src] = 0;
    inqueue[src] = true;
    queue.push_back(src);
    while (!queue.empty()) {
        int_t front = queue.front();
        queue.pop_front();
        inqueue[front] = false;
        inqN[front]++;
        if (inqN[front] > n)
            return false;
        for (const auto& edge : graph[front]) {
            if (dis[edge.to] > dis[front] + edge.weight) {
                dis[edge.to] = dis[front] + edge.weight;
#ifdef DEBUG
                cout << "dis " << edge.to << " to " << dis[edge.to] << endl;
#endif
                if (!inqueue[edge.to]) {
                    if (!queue.empty() && dis[edge.to] < dis[queue.front()])
                        queue.push_front(edge.to);
                    else
                        queue.push_back(edge.to);
                    inqueue[edge.to] = true;
                }
            }
        }
    }
    return true;
}

bool check(int_t x) {
#ifdef DEBUG
    cout << "checking " << x << endl;
#endif
    clear();
    for (int_t i = 1; i <= n; i++) {
        pushLEQ(i - 1, i, 0);
    }
    for (int_t i = 1; i <= n; i++) {
        pushLEQ(i, i - 1, -1);
    }
    for (int_t i = 1; i <= m1; i++) {
        const auto& ref = cond1[i];
        pushLEQ(ref.left - 1, ref.right, ref.val);
    }
    for (int_t i = 1; i <= m2; i++) {
        const auto& ref = cond2[i];
        pushLEQ(ref.right, ref.left - 1, ref.val - x);
    }
    pushLEQ(0, n, x);
    pushLEQ(n, 0, -x);
    auto ret = SPFA(n, 0);
#ifdef DEBUG
    cout << "check " << x << " = " << ret << endl;
#endif
    return ret;
}

int main() {
    std::ios::sync_with_stdio(false);
    int_t T;
    cin >> T;
    while (T--) {
        cin >> n >> m1 >> m2;
        for (int_t i = 1; i <= m1; i++) {
            auto& ref = cond1[i];
            cin >> ref.left >> ref.right >> ref.val;
        }
        for (int_t i = 1; i <= m2; i++) {
            auto& ref = cond2[i];
            cin >> ref.left >> ref.right >> ref.val;
        }
        int_t left = 0, right = n;
        int_t result = INF;
        while (left + 1 < right) {
            int_t mid = (left + right) / 2;
            if (check(mid)) {
                result = std::min(result, mid);
                right = mid - 1;
            } else
                left = mid + 1;
        }
        for (int_t i = left; i <= right; i++)
            if (check(i))
                result = std::min(result, i);
        cout << result << endl;
    }

    return 0;
}

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

#include <algorithm>

#include <deque>

#include <iostream>

#include <vector>

using std::cin;

using std::cout;

using std::endl;

using int_t = int;

1. x_{n-1}+0<=x_n(前缀和不减)

2. x_n+(-1)<=x_{n-1}前缀和要么加1要么不变

3. x_{l-1}+x<=x_r 区间染色数下限

4. x_r +(x-M) <= x_{l-1} 区间外染色数下限

5. x_0+M<=x_n 一共至少染M个

6. x_n+(-M)<=x_0 一共至多染M个(与5一起保证恰好染M个)

const int_t LARGE = 3010;

const int_t INF = 0x3fffffff;

int_t dis[LARGE + 1];

int_t inqN[LARGE];

bool inqueue[LARGE + 1];

struct Edge {

int_t to, weight;

Edge(int_t v, int_t w) : to(v), weight(w) {}

};

struct Limitation {

int_t left, right, val;

} cond1[LARGE + 1], cond2[LARGE + 1];

int_t n, m1, m2;

//不等式A+X<=B变为边(A,B)，长度-X

std::vector<Edge> graph[LARGE + 1];

void clear() {

std::fill(dis, dis + 1 + n, INF);

std::fill(inqueue, inqueue + 1 + n, false);

std::fill(inqN, inqN + 1 + n, 0);

for (int_t i = 0; i <= n; i++)

graph[i].clear();

}

void pushEdge(int_t u, int_t v, int_t w) {

#ifdef DEBUG

cout << "edge " << u << " to " << v << " val " << w << endl;

#endif

graph[u].push_back(Edge(v, w));

}

//添加不等式x_a+v<=x_b

void pushLEQ(int_t a, int_t b, int_t v) {

#ifdef DEBUG

cout << "cond x_" << a << " + " << v << " <= x_" << b << endl;

#endif

pushEdge(b, a, -v);

}

bool SPFA(int_t src, int_t target) {

std::deque<int_t> queue;

dis[src] = 0;

inqueue[src] = true;

queue.push_back(src);

while (!queue.empty()) {

int_t front = queue.front();

queue.pop_front();

inqueue[front] = false;

inqN[front]++;

if (inqN[front] > n)

return false;

for (const auto& edge : graph[front]) {

if (dis[edge.to] > dis[front] + edge.weight) {

dis[edge.to] = dis[front] + edge.weight;

#ifdef DEBUG

cout << "dis " << edge.to << " to " << dis[edge.to] << endl;

#endif

if (!inqueue[edge.to]) {

if (!queue.empty() && dis[edge.to] < dis[queue.front()])

queue.push_front(edge.to);

else

queue.push_back(edge.to);

inqueue[edge.to] = true;

}

return true;

}

bool check(int_t x) {

#ifdef DEBUG

cout << "checking " << x << endl;

#endif

clear();

for (int_t i = 1; i <= n; i++) {

pushLEQ(i - 1, i, 0);

}

for (int_t i = 1; i <= n; i++) {

pushLEQ(i, i - 1, -1);

}

for (int_t i = 1; i <= m1; i++) {

const auto& ref = cond1[i];

pushLEQ(ref.left - 1, ref.right, ref.val);

}

for (int_t i = 1; i <= m2; i++) {

const auto& ref = cond2[i];

pushLEQ(ref.right, ref.left - 1, ref.val - x);

}

pushLEQ(0, n, x);

pushLEQ(n, 0, -x);

auto ret = SPFA(n, 0);

#ifdef DEBUG

cout << "check " << x << " = " << ret << endl;

#endif

return ret;

}

int main() {

std::ios::sync_with_stdio(false);

int_t T;

cin >> T;

while (T--) {

cin >> n >> m1 >> m2;

for (int_t i = 1; i <= m1; i++) {

auto& ref = cond1[i];

cin >> ref.left >> ref.right >> ref.val;

}

for (int_t i = 1; i <= m2; i++) {

auto& ref = cond2[i];

cin >> ref.left >> ref.right >> ref.val;

}

int_t left = 0, right = n;

int_t result = INF;

while (left + 1 < right) {

int_t mid = (left + right) / 2;

if (check(mid)) {

result = std::min(result, mid);

right = mid - 1;

} else

left = mid + 1;

}

for (int_t i = left; i <= right; i++)

if (check(i))

result = std::min(result, i);

cout << result << endl;

}

return 0;

}

officeyutong

不止有算法竞赛

CFGYM102394A CCPC2019哈尔滨A Artful Paintings

赞过：

相关

发表回复取消回复

共享此文章：

赞过：

相关

发表回复 取消回复

发表回复取消回复