注意：本学期 CS101 PA 的所有 C++ 代码都采用 C++20 标准。如果您使用 GCC 或 Clang，您需要在编译时设置 -std=c++20 。

如果您看到类似这样的报错

g++-9: error: unrecognized command line option ‘-std=c++20’; did you mean ‘-std=c++2a’?

说明您的编译器版本过低，请安装更高版本的编译器。目前 GCC 13 几乎已经将 C++20 除 modules 外的全部新特性实现完毕，我们推荐使用 GCC 13。

Problem 1. Master of Linear Algebra#

There are $m$ vectors $\bm v_i(i=1,\cdots,m)$ in $\R^n$ , where each vector $\bm v_i$ has a value $c_i$ . Each vector $\bm v_i$ consists of only a consecutive interval of standard basis vectors $\bm{e}_{l_i}\dots \bm e_{r_i}$ . In other words, there exist $1\le l_i\le r_i\le n$ such that $\bm v_i = \bm e_{l_i} + \bm e_{l_i+1} + \bm e_{l_i+2} + \dots + \bm e_{r_i}$ , i.e.

\bm v_i = (0,\cdots,0,\underbrace{1,\cdots,1}_{\text{from }l_i\text{ to }r_i},0,\cdots,0).

It means that the $l_i$ -th entry to $r_i$ -th entry of $\bm v_i$ are $1$ , and others are $0$ .

Now your task is to select a linearly independent subset $S$ of vectors $\bm v_i$ , maximizing the sum of the value (the $c_i$ ‘s) of the selected vectors.

Linear independence: The vectors $\bm v_1,\bm v_2,\cdots,\bm v_m$ are said to be linearly independent if there do not exist scalars $a_1,\cdots,a_m$ , which are not all zero, such that
$\sum_{i=1}^ma_i\bm v_i = \bm 0.$

Input format#

The first line contains two integers $m,n$ separated by space, denoting there are $m$ vectors $(1\le m \le 600000, 1\le n\le 200000)$ .

Then follow $m$ lines, the $i$ -th of which contains 3 integers $l_i, r_i, c_i$ separated by space, denoting the $i$ -th vector is $\bm v_i=\sum_{j=l_i}^{r_i}\bm e_j$ and has value $c_i(1\le c_i\le 10^9)$ .

It is guaranteed that for any $1\le i,j\le n$ and $i\neq j$ , either $l_i\neq l_j$ or $r_i\neq r_j$ holds.

Output format#

Output an integer denoting the maximum sum of values of linearly independent vectors.

Examples#

Input 1#

Output 1#

Sample 1 Explanation#

The vectors are

\begin{aligned} \bm v_1&=(1,0,0,0),\\ \bm v_2&=(0,1,1,0),\\ \bm v_3&=(0,0,0,1),\\ \bm v_4&=(0,0,1,1),\\ \bm v_5&=(0,1,1,1),\\ \bm v_6&=(0,1,0,0). \end{aligned}

Choose four vectors $\left\{\bm v_1,\bm v_2,\bm v_4,\bm v_6\right\}$ . The answer is $10 + 15 + 30 + 31 = 86$ .

Input 2#

18 12
5 7 747599713
3 4 757926887
3 6 382811701
4 6 97461676
4 9 710404753
2 9 487547197
2 6 596396727
2 2 608843003
4 4 845337000
4 7 18671691
11 11 135958130
11 12 452842130
1 12 528936929
1 5 812188014
6 8 535007878
12 12 617497619
9 12 737458124
6 12 583189872

Output 2#

7469683842

Sample 2 Explanation#

Choose 11 vectors $\left\{\bm v_1,\bm v_2,\bm v_5,\bm v_7,\bm v_8,\bm v_9,\bm v_{12},\bm v_{14},\bm v_{16},\bm v_{17},\bm v_{18}\right\}$ .

Problem 2. VCG auction#

$n$ buyers want to compete for $m$ items through auction.

The $i$ -th buyer wants to buy $c_i$ items at a price for $v_i$ . Note that $v_i$ also means the $i$ -th buyer’s valuation of the items.

The VCG auction allocates the $m$ items which maximize the sum of the valuations of those who get $c_i$ items as he/she wants.

$V=(v_1,v_2,...,v_n)$ ;
$C=(c_1,c_2,...,c_n)$ ;
$\operatorname{VA}(V,C)=\left\{A\in2^{\{1,2,...,n\}}:\sum\limits_{i\in A}c_i\leqslant m\right\}$ , which means the set of all Valid Allocations to the $n$ buyers. Valid means that $m$ items are enough to be allocated.
$\operatorname{MSV}(V,C)=\max\limits_{A\in\operatorname{VA}(V,C)}\sum\limits_{i\in A}v_i$ , which means the Maximal Sum of the Valuations of those who gets $c_i$ items as he/she wants.
$A_M(V,C)\in \mathop{\arg\max}\limits_{A\in\operatorname{VA}(V,C)}\sum\limits_{i\in A}v_i$ , which means the valid allocation that maximizes the sum of the valuations. The buyers in $A_M(V,C)$ win the auction and get the items they want.
$V_{-i}=(v_1,v_2,...,v_{i-1},v_{i+1},...,v_n)$ , which means excluding $v_i$ from $V$ ;
$C_{-i}=(c_1,c_2,...,c_{i-1},c_{i+1},...,c_n)$ , which means excluding $c_i$ from $C$ ;
$p_i=v_i+\operatorname{MSV}(V_{-i},C_{-i})-\operatorname{MSV}(V,C)$ , which is the definition of the payment of the $i$ -th buyer $i\in A_M(V,C)$ if he/she gets the $c_i$ items.

Your task is to compute $A_M(V,C)$ and their payments. If there is more than one choice of $A_M(V,C)$ , please choose the lexicographically least one.

Input format#

The first line contains two positive integers $n$ and $m$ , separated by a space.

For the following $n$ lines:

The $i$ -th line contains two positive integers $v_i$ and $c_i$ , separated by a space.

Output format#

On the first line, print $A_M(V,C)$ (lexicographically least one). The numbers are separated by spaces.

On the second line, print $p_i$ for all $i\in A_M(V,C)$ . The numbers are separated by spaces.

Testing on OJ#

There are 20 testcases on OJ. For the first 10 testcases, your program (assuming it is named foo.cc) is compiled with

g++ foo.cc -o foo -std=c++20 -Wall -Wpedantic -Wextra -Werror -DONLINE_JUDGE -fmax-errors=3 -fdiagnostics-color=always -fsanitize=undefined -fsanitize=address -g

For testcases 11 ~ 20, your program is compiled with

g++ foo.cc -o foo -std=c++20 -Wall -Wpedantic -Wextra -Werror -DONLINE_JUDGE -fmax-errors=3 -fdiagnostics-color=always -O2

Due to the OJ settings, there is no way of running a single testcase in pretest (运行自测). You can enter your input data there and see the output. For pretesting, the program will be compiled with the same command as for the first 10 testcases.

Data constraints#

$1\leqslant n,m\leqslant 6000$ .
$1\leqslant v_i\leqslant 10^9, 1\leqslant c_i\leqslant m$ .

If you implement your algorithm in $\Theta(n^2m)$ time, you will receive about 50 pts.

If you implement your algorithm in $\Theta(nm)$ time, you will receive about 100 pts.

Examples#

Input 1#

2 2
2 1
3 2

Output 1#

2
2

Explanation 1#

$v_1=2,c_1=1$ ;
$v_2=3,c_2=2$ ;
$\operatorname{MSV}(V,C)=3,A_M(V,C)=\{2\}$ ;
$\operatorname{MSV}(V_{-2},C_{-2})=2,A_M(V_{-2},C_{-2})=\{1\},p_2=3+2-3=2$ .

Input 2#

Output 2#

1 3
1 3

Explanation 2#

$v_1=1,c_1=1$ ;
$v_2=2,c_2=2$ ;
$v_3=3,c_1=3$ ;
$v_4=2,c_2=2$ ;
$\operatorname{MSV}(V,C)=4,A_M(V,C)\in\{\ \{1,3\},\ \{2,4\}\}$ , choose the lexicographically least one $\{1,3\}$
$\operatorname{MSV}(V_{-1},C_{-1})=4,A_M(V_{-1},C_{-1})=\{2,4\},p_1=1+4-4=1$ ;
$\operatorname{MSV}(V_{-3},C_{-3})=4,A_M(V_{-3},C_{-3})=\{2,4\},p_3=3+4-4=3$ .

Problem 3. Shortest path#

This problem consists of three subtasks: the Bellman-Ford algorithm, the Dijkstra’s algorithm, and the difference constraints problem.

Please go to Piazza Resources to download the related materials first.

The `Graph` class#

graph.hpp is a header file defining a Graph class that represents a directed, edge-weighted graph $G=(V,E)$ using adjacency lists. For simplicity, we assume that $V=\{0,1,\cdots,n-1\}$ and that the edge weights are integers. Considering that you might have not written any graph-related code before, we have implemented two basic functions for you as demonstration:

The Breadth-First Search algorithm, which has the following signature
```
void bfs(VertexID start, std::invocable<VertexID> auto callback) const;
```
start is the id of the vertex where the traversal begins. callback is a callable object that is called every time a vertex is visited. For example, the following code (see examples/graph_example.cpp) performs BFS on the graph graph and prints the id of the visited vertices in order.
```
graph.bfs(0, [](auto x) { std::cout << x << ' '; });
```
The naive $O\left(V^2\right)$ Dijkstra’s algorithm, which has the following signature
```
std::vector<Weight> dijkstra(VertexID source) const;
```
source is the id of the source vertex. This function returns a std::vector<Weight>, in which the element indexed i is the length of the shortest path from source to the vertex i, or Graph::infinity if no path exists.
The behavior is undefined if there exists an edge with negative weight.
By saying “the behavior is undefined”, we mean that you don’t need to care about this case. Do not waste your effort detecting it.
The implementation of this function is in graph.cpp, which you need to overwrite (See below).

Read through the code we have provided in graph.cpp, graph.hpp and examples/graph_example.cpp and make sure you have understood the design. To compile and run graph_example.cpp, refer to compile and run.

Note: Your submission will not contain the contents in graph.hpp. Any modification to that file (e.g. adding a member to the class Graph) will have no effect.

Subtask 1: The Bellman-Ford algorithm#

First, you need to implement the Bellman-Ford algorithm that calculates the length of the shortest path from a given source vertex to each vertex, or reports that there is a negative cycle reachable from source. It is a member function of Graph that has the following signature

std::optional<std::vector<Weight>> bellmanFord(VertexID source) const;

std::optional<T> is a special standard library type that represents either an object of type T, or nothing (represented by std::nullopt). You can refer to examples/equation.cpp to see an example of using it.

This function should return std::nullopt if the graph contains a negative cycle reachable from source. Otherwise, it should return a vector of numbers, in which the element indexed i is the length of the shortest path from source to the vertex i, or Graph::infinity if no path exists. This function should run in $O(VE)$ time with $O(V)$ extra space.

Write your implementation in graph.cpp.

Subtask 2: The Dijkstra’s algorithm#

In graph.cpp, there is an implementation of the naive Dijkstra’s algorithm whose time complexity is $O\left(V^2\right)$ . Suppose now the graph is not so dense, or more specifically, $E=o\left(V^2/\log V\right)$ . Overwrite this function to make it run within $O(E\log V)$ time, with $O(V)$ extra space.

You may need std::priority_queue. We have provided two examples of using it: examples/priqueue.cpp and examples/huffman.cpp. The latter is a program that computes the Huffman codes given the frequencies of characters.

By default, std::priority_queue<T> uses std::less<T> (which is operator<) to compare elements and models a max-heap. If you need a min-heap, just pass std::greater<> as the third template argument (see details in the examples).
We have seen some inexperienced students overload operator< to do the work that should have been done by operator> (e.g. return lhs.something > rhs.something;), or pass negated values to the max-heap to fake a min-heap. You should never do that.

Subtask 3: System of difference constraints#

In a system of difference constraints (or, difference constraints problem), there are $n$ variables $x_0,x_1,\cdots,x_{n-1}$ and $m$ constraints on these variables, where the $k$ -th constraint ( $0\leqslant k<m$ ) is of the form

x_{u_k}-x_{v_k}\leqslant c_k

where $0\leqslant u_k,v_k<n$ , and $u_k\neq v_k$ . We want to find a solution to the given difference constraints problem, that is, to assign the variables with values so that all the constraints are satisfied.

For example, the following is a system of difference constraints with $5$ variables and $8$ constraints:

\begin{aligned} x_0-x_1&\leqslant 0,\\ x_0-x_4&\leqslant -1,\\ x_1-x_4&\leqslant 1,\\ x_2-x_0&\leqslant 5,\\ x_3-x_0&\leqslant 4,\\ x_3-x_2&\leqslant -1,\\ x_4-x_2&\leqslant -3,\\ x_4-x_3&\leqslant -3. \end{aligned}

One solution to this problem is $\left(x_0,x_1,x_2,x_3,x_4\right)=(-5,-3,0,-1,-4)$ , which you can verify directly by checking each inequality. Note that a system of difference constraints usually have infinitely many solutions, but some systems may have no solutions at all. The following is a system with $3$ variables and $3$ constraints that have no solutions:

\begin{aligned} x_0-x_1&\leqslant -1,\\ x_1-x_2&\leqslant -1,\\ x_2-x_0&\leqslant -1. \end{aligned}

A system of difference constraints can be modeled as a graph, and then solved by solving a single-source shortest-path problem on the graph. Read Section 24.4 of Introduction to Algorithms, Third Edition which is available in Piazza Resources.

The difference constraints problem that you need to solve will be presented as the class Problem in problem.hpp. Read through the code in problem.hpp and understand the structure of that class. Note that we have implemented some useful functions for you, such as hasNegativeConstant(), getNumVars() and getConstraints().

Your task is to implement the solve function in main.cpp, which has the signature

std::optional<Problem::Solution> solve(const Problem &problem);

It solves the given difference constraints problem problem, and returns the solution to it or std::nullopt if it has none. A solution is of type Problem::Solution i.e. std::vector<Problem::Value> in which the element indexed i is the value assigned to the variable $x_i$ .

For testcase 1~5, $c_k$ may be negative, and your algorithm should run within $O\left(n^2+nm\right)$ time. For testcase 6~10, $c_k$ are non-negative, and your algorithm should run within $O((n+m)\log n)$ time.

Compile and run#

Basic knowledge#

Read {% post_link CS101/Compile-Basics Compile Basics%} if you need.

Compile multiple files#

The functions Graph::dijkstra and Graph::bellmanFord are defined in graph.cpp. Therefore, every time you compile a program that calls those functions, graph.cpp should be compiled and linked as well. You will see an error like

/usr/bin/ld: /tmp/ccxICQ7U.o: in function `main':
graph_example.cpp:(.text+0x15e): undefined reference to `Graph::dijkstra(unsigned long) const'
collect2: error: ld returned 1 exit status

if you did not link them correctly. The simplest way is to also pass the path to graph.cpp as an argument to the compiler. For example, to compile solve.cpp, cd to the directory attachments first, and then

g++ solve.cpp graph.cpp -o solve -std=c++20

To compile examples/graph_example.cpp: If the current working directory is attachments,

g++ examples/graph_example.cpp graph.cpp -o examples/graph_example -std=c++20

This will generate an executable named graph_example (graph_example.exe on Windows) in the directory attachments/examples. If the current working directory is attachments/examples,

g++ graph_example.cpp ../graph.cpp -o graph_example -std=c++20

will do the same thing.

It is so annoying to enter such a long command every time! You can press ↑ to obtain your command history.

VSCode configurations#

Read VSCodeConfig.md if you need.

Submission#

Create a zip file submission.zip containing graph.cpp and solve.cpp, and then submit submission.zip to the OJ. You can cd to attachments, and then run the following command to create it:

zip -r submission.zip graph.cpp solve.cpp

Note that the files graph.cpp and solve.cpp should be placed directly in the zip file.

评分#

评分由 OJ 分数（60%）和线下 check （40%）两部分构成。线下 check 会在此次作业结束时间之后进行。

注：线下 check 也带有检查学术诚信的含义，当然这不是唯一的手段。如果被认定为抄袭， OJ 的分数也会作废，并且会有惩罚。特别强调，抄袭来自 generative AI 的代码和抄袭网上的代码是同等处理的，我们建议您在写作业时关闭一切generative AI 工具。

Problem 1. Master of Linear Algebra#

Input format#

Output format#

Examples#

Input 1#

Output 1#

Sample 1 Explanation#

Input 2#

Output 2#

Sample 2 Explanation#

Problem 2. VCG auction#

Input format#

Output format#

Testing on OJ#

Data constraints#

Examples#

Input 1#

Output 1#

Explanation 1#

Input 2#

Output 2#

Explanation 2#

Problem 3. Shortest path#

The Graph class#

Subtask 1: The Bellman-Ford algorithm#

Subtask 2: The Dijkstra’s algorithm#

Subtask 3: System of difference constraints#

Compile and run#

Basic knowledge#

Compile multiple files#

VSCode configurations#

Submission#

评分#

The `Graph` class#