P10541 [THUPC 2024 Finals] R&D Plan

Seeing that several large-model startup companies have recently obtained huge funding, as an “alchemy master” you feel tempted and decide to enter the market and build products yourself. After some整理 (sorting things out), you find that there are currently $m$ kinds of products that will sell very well after being launched. After launching product $i$, the expected profit is $g_i$. These $m$ products involve $n$ kinds of technologies. There are $p$ technology-product dependency relations $(u,v)$, meaning technology $u$ is a prerequisite technology for product $v$. For each product, you must obtain all its prerequisite technologies before you can launch it. For technology $j$, you can choose to pay a cost $f_j$ to buy it directly from other companies, or pay a cost $h_j$ to obtain it through R&D. R&D requires certain conditions: there are $q$ technology-technology dependency relations $(a,b)$, meaning technology $a$ is a prerequisite technology for technology $b$. Then, you can obtain technology $j$ through R&D only after you have obtained all prerequisite technologies of technology $j$. If a technology has no prerequisites, then you can obtain it directly through R&D. It is guaranteed that the technology-technology dependency relations form a directed acyclic graph, i.e., no cyclic dependencies will occur (and naturally there will be no self-loops). The profit of a plan equals the total profit of the launched products minus the total cost of obtaining technologies. Now, as a businessman, you want to research some technologies and launch some products to maximize your profit. For simplicity, you only need to output the maximum profit value.

The first line contains four positive integers $n,m,p,q$. It is guaranteed that $2 \le n \le 100$, $1 \le m \le 100$, $1 \le p\leq nm$, $1 \le q\leq \frac{n(n-1)}{2}$, representing the total number of technologies, the total number of products, the number of technology-product dependency relations, and the number of technology-technology dependency relations. The next line contains $n$ integers $f_i$, representing the cost of buying technology $i$ directly. The next line contains $n$ integers $h_i$, representing the cost of researching technology $i$ based on its prerequisite technologies. The next line contains $m$ integers $g_i$, representing the profit obtained after launching product $i$. The next $p$ lines each contain two integers $u_i,v_i$, representing a technology-product dependency relation $(u_i,v_i)$. It is guaranteed that $1 \le u_i \le n$, $1 \le v_i \le m$, and all input $(u_i,v_i)$ are pairwise distinct. The next $q$ lines each contain two integers $a_i,b_i$, representing a technology-technology dependency relation $(a_i,b_i)$. It is guaranteed that $1 \le a_i \ne b_i \le n$, all input $(a_i,b_i)$ are pairwise distinct, and they do not form cyclic dependencies. It is guaranteed that all input numbers are non-negative integers not exceeding $10^9$.

Output an integer, representing the maximum profit among all plans.

The optimal plan is to research technology 1, buy technology 3, and research technology 4 in order. Then we can launch products 1, 4, and 5. The profit is $(2+8+8)-(1+6+3)=8$. **Source and Acknowledgements** From the THUPC2024 (Tsinghua University Student Programming Contest and Invitational Contest) Finals. Thanks to THUSAA for providing this problem. For testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository: . Translated by ChatGPT 5