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.


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

hide comments
2024-01-19 23:57:18 Oleg
Constraints are too relaxed. Time limit allows calculate all Q operations independently.
2022-09-02 17:49:28 [Rampage] Blue.Mary
@simes: The 2nd sample output is wrong. My AC solution output 947 and 899 for the last two "Q" queries.
[simes]: fixed.

Last edit: 2022-09-02 21:54:41
2020-10-22 18:21:44 [Rampage] Blue.Mary
The 2nd sample output is wrong. My AC solution output 947 and 899 for the last two "Q" queries.
2015-10-09 10:27:11 Takanori MAEHARA
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.
2013-12-11 20:49:39 ABHISHEK
@xiaodao I don't understand this one "Q : Query the current maximum weighted matching"
2013-01-06 08:28:06 xiaodao
[0, n)
2013-01-06 08:28:06 xyz
what's the meaning of "X 0 ..."
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.