Mario and Luigi
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Mario and Luigi are very lazy guys. These are not the guys from some game, these are the ones playing games all the time. Recently, they bought a new game named "Graph Vertices chooser".
The rules of this game are pretty simple. It's a two player game with each player taking alternating turns starting with Mario. You are given a weighed graph. All the vertices are initially unmarked. In each turn, a player chooses an unmarked vertex and mark it to red or black color (Mario marks red whereas Luigi marks black). The game ends when there is no any unmarked vertex left. After the end of the game, Mario's score will be weight of all the edges in graph such that both the end points of the edge are colored red. Similarly, score of Luigi is sum of weight of edges with both end points being black.
Mario would like to maximize difference between his and Luigi points, while Luigi would like to minimize the difference between Mario's and his score. Both player optimally.
Now, you are the one who decided to be the coach of both the players. You want to create many graphs for Mario and Luigi to train. For that, you decided to take a graph H of N vertices. Initially, there is no edge in graph H. One by one, you will add an edge in the graph H and ask the both the players to play on the newly created graph. You will add M such edges. For each of the M graphs, you have to tell the difference between points of Mario and Luigi at the end of the game, when they play the game on that graph. Note that self loops and multi-edges are allowed to exist.
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two integers N and M denoting number of vertexes and number of edges to be added by the coach.
Each of the next M lines contains description of each edge u, v, c, denoting two vertexes and cost of edge.
For each test case, output M lines containing the difference between Mario's and Luigi's points after adding the i-th edge, for each i.
You should add edges one by one (with same order as they follows in input), and every time output the difference between points of Mario and Luigi at the end of each game.
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 105
- 1 ≤ u, v ≤ N
- 1 ≤ c ≤ 109
- Self loops and multiple edges are allowed.
- Subtask 1 (10 points): 1 ≤ N ≤ 10, 1 ≤ M ≤ 100
- Subtask 2 (40 points): 1 ≤ N, M ≤ 2000
- Subtask 3 (50 points): original constraints
Input: 1 5 4 1 2 1 1 3 1 1 4 1 1 5 1 Output: 0 1 1 2
|Tags||april16, furko, graphs, hard, segment-tree, treaps|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.