DAP - Dynamic Assignment Problem
Description
You‘ve been given a N×N matrix {W_ij} containing the cost of a weighted bipartite graph, on this graph, you need to implement the following operations:
- C i j w : Change Wij to w.
- X i x0 x1 ... xn-1 : Change all Wij to xj.
- Y i y0 y1 ... yn-1 : Change all Wji to yj.
- A : Add a new pair of node to the current bipartite graph, then increase N by 1. The weight of those 2n+1 new edges will be set to 0 by default.
- Q : Query the current maximum weighted matching.
Input
N
(... following the N×N matrix ...)
M
(... following the M operation ......)
Output
...
(for each query, simply print the result.)
Example
Input 1:
2
1 0
0 1
3
Q
C 0 1 9
Q
Output 1:
2
9
Input 2:
10
76 98 80 30 87 84 78 75 53 26
85 7 83 15 21 91 47 84 82 78
36 39 49 64 71 14 53 2 82 21
83 31 32 30 78 19 46 95 50 55
50 76 63 54 99 55 50 16 29 26
58 74 77 32 3 91 90 18 34 3
56 23 2 78 84 83 71 41 32 54
53 75 39 29 61 25 42 79 58 2
19 13 65 94 9 33 61 5 1 70
34 56 45 37 72 98 47 40 80 79
20
Q
Y 3 62 90 89 41 58 56 34 55 53 53
X 0 7 30 30 76 2 48 8 18 89 88
Q
C 2 0 3
C 3 0 0
C 8 0 2
C 1 0 3
C 1 0 6
C 5 0 9
Q
A
X 10 93 8 56 40 4 56 30 32 59 11 52
Y 10 84 62 26 13 66 21 53 23 54 81 52
Q
Y 9 13 38 99 50 20 25 59 7 6 77 82
C 4 0 8
C 6 0 6
C 10 0 8
Q
Output 2:
870
849
844 947 899
Restriction
We guarantee the N will never be more than 100 even during the running time.
The total operation M will less than 10000, and among them the Query Operation will be less than 1000.
hide comments
Oleg:
2024-01-19 23:57:18
Constraints are too relaxed. Time limit allows calculate all Q operations independently. |
|
[Rampage] Blue.Mary:
2022-09-02 17:49:28
@simes: The 2nd sample output is wrong. My AC solution output 947 and 899 for the last two "Q" queries.
|
|
[Rampage] Blue.Mary:
2020-10-22 18:21:44
The 2nd sample output is wrong. My AC solution output 947 and 899 for the last two "Q" queries. |
|
Takanori MAEHARA:
2015-10-09 10:27:11
I don't understand the 2nd sample input. Why are the 3rd and 4th solutions same? I think there exists a heavier matching since new vertices are added. |
|
ABHISHEK:
2013-12-11 20:49:39
@xiaodao I don't understand this one "Q : Query the current maximum weighted matching" |
|
xiaodao:
2013-01-06 08:28:06
[0, n) |
|
xyz:
2013-01-06 08:28:06
what's the meaning of "X 0 ..."
|
Added by: | xiaodao |
Date: | 2012-11-14 |
Time limit: | 1s-10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own Problem |