308468: CF1525F. Goblins And Gnomes
Memory Limit:512 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Goblins And Gnomes
题意翻译
### 题意 有一个 $n$ 个点的 DAG,现在有 $k$ 波进攻,第 $i$ 波有 $i$ 个人,它们每个人会选择一条 DAG 上的路径,并占领这个路径上的所有点,路径之间是不能相交的。第 $i$ 波进攻前可以做一些准备,可以花 $1$ 秒关闭某个点的所有入边,或关闭某个点的所有出边。第 $i$ 波进攻有个参数 $a_i,b_i$,如果花费了 $t_i$ 时间准备,如果不会所有点都被占领,就会获得收益 $\max(0,a_i-tb_i)$,如果被占领就不会有收益了,求最大收益,输出方案。 $n \leq 50$。题目描述
Monocarp plays a computer game called "Goblins and Gnomes". In this game, he manages a large underground city of gnomes and defends it from hordes of goblins. The city consists of $ n $ halls and $ m $ one-directional tunnels connecting them. The structure of tunnels has the following property: if a goblin leaves any hall, he cannot return to that hall. The city will be attacked by $ k $ waves of goblins; during the $ i $ -th wave, $ i $ goblins attack the city. Monocarp's goal is to pass all $ k $ waves. The $ i $ -th wave goes as follows: firstly, $ i $ goblins appear in some halls of the city and pillage them; at most one goblin appears in each hall. Then, goblins start moving along the tunnels, pillaging all the halls in their path. Goblins are very greedy and cunning, so they choose their paths so that no two goblins pass through the same hall. Among all possible attack plans, they choose a plan which allows them to pillage the maximum number of halls. After goblins are done pillaging, they leave the city. If all halls are pillaged during the wave — Monocarp loses the game. Otherwise, the city is restored. If some hall is pillaged during a wave, goblins are still interested in pillaging it during the next waves. Before each wave, Monocarp can spend some time preparing to it. Monocarp doesn't have any strict time limits on his preparations (he decides when to call each wave by himself), but the longer he prepares for a wave, the fewer points he gets for passing it. If Monocarp prepares for the $ i $ -th wave for $ t_i $ minutes, then he gets $ \max(0, x_i - t_i \cdot y_i) $ points for passing it (obviously, if he doesn't lose in the process). While preparing for a wave, Monocarp can block tunnels. He can spend one minute to either block all tunnels leading from some hall or block all tunnels leading to some hall. If Monocarp blocks a tunnel while preparing for a wave, it stays blocked during the next waves as well. Help Monocarp to defend against all $ k $ waves of goblins and get the maximum possible amount of points!输入输出格式
输入格式
The first line contains three integers $ n $ , $ m $ and $ k $ ( $ 2 \le n \le 50 $ ; $ 0 \le m \le \frac{n(n - 1)}{2} $ ; $ 1 \le k \le n - 1 $ ) — the number of halls in the city, the number of tunnels and the number of goblin waves, correspondely. Next $ m $ lines describe tunnels. The $ i $ -th line contains two integers $ u_i $ and $ v_i $ ( $ 1 \le u_i, v_i \le n $ ; $ u_i \ne v_i $ ). It means that the tunnel goes from hall $ u_i $ to hall $ v_i $ . The structure of tunnels has the following property: if a goblin leaves any hall, he cannot return to that hall. There is at most one tunnel between each pair of halls. Next $ k $ lines describe the scoring system. The $ i $ -th line contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i \le 10^9 $ ; $ 1 \le y_i \le 10^9 $ ). If Monocarp prepares for the $ i $ -th wave for $ t_i $ minutes, then he gets $ \max(0, x_i - t_i \cdot y_i) $ points for passing it.
输出格式
Print the optimal Monocarp's strategy in the following format: At first, print one integer $ a $ ( $ k \le a \le 2n + k $ ) — the number of actions Monocarp will perform. Next, print actions themselves in the order Monocarp performs them. The $ i $ -th action is described by a single integer $ b_i $ ( $ -n \le b_i \le n $ ) using the following format: - if $ b_i > 0 $ then Monocarp blocks all tunnels going out from the hall $ b_i $ ; - if $ b_i < 0 $ then Monocarp blocks all tunnels going into the hall $ |b_i| $ ; - if $ b_i = 0 $ then Monocarp calls the next goblin wave. You can't repeat the same block action $ b_i $ several times. Monocarp must survive all waves he calls (goblins shouldn't be able to pillage all halls). Monocarp should call exactly $ k $ waves and earn the maximum possible number of points in total. If there are several optimal strategies — print any of them.
输入输出样例
输入样例 #1
5 4 4
1 2
2 3
4 3
5 3
100 1
200 5
10 10
100 1
输出样例 #1
6
-2 -3 0 0 0 0
输入样例 #2
5 4 4
1 2
2 3
4 3
5 3
100 100
200 5
10 10
100 1
输出样例 #2
6
0 -3 0 0 1 0
输入样例 #3
5 10 1
1 2
1 3
1 4
1 5
5 2
5 3
5 4
4 2
4 3
2 3
100 100
输出样例 #3
6
1 2 3 4 5 0