itemized discussion
- ABC004D D - Marble
-
-
Xi stones are placed in three locations.
-
Assign up to one of these to an unspecified number of squares.
- The problem condition is infinite number of pieces, but realistically, a number about the sum of Xi is sufficient.
-
Cost Cij is the distance from the place where it is located to the destination
-
- PAST3O
-
-
Assign N locations for M objects in each of the three rounds
-
At this time, the reward Rij is obtained
-
However, the cost Djk depends on how many k were finally assigned to location j
-
This cost is progressive.
-
So it can be expressed using Cjk=Djk-Dj(k-1)
- Because they are chosen from the cheapest
- Least cost flow where costs are not proportional to flow rate
- Progressive cost expressed as a difference
-
- ACLPC E
- Up to K in the same row
- = Select up to K from N locations
- It is important to note that not just K pieces
- Acknowledge the choice not to choose by creating a side path.
- Two-dimensional cells are bipartite graphs
- The squares correspond to the edges of a bipartite graph.
- F - Three Knights and a Dog
- Maximum-Cup 2013: F - Three Knights and a Dog - kmjp’s blog
- Choose the one with the smallest cost among those with the largest rewards to be obtained.
- The number of choices is M, the number of pieces chosen L=min(N, M)
- Rewards are used to construct the graph instead of putting them on the edges.
- Sort in order of reward Rj, and select the remaining L-A pieces from the B pieces with the same score as the Lth piece, with A as the number of pieces to be selected with a definite score higher than the Lth piece.
- No.1301 Strange Graph Shortest Path - yukicoder
- undirected graph
- Shortest path from vertex 1 to N and back to 1
- Can go through the same side twice.
- 1st cost ci, 2nd cost di, di>=ci
- Flow rate 2
- Why is this okay?
- If you’re going through an edge only once, you can go through in the opposite direction for the same cost.
- When you’re going through it twice, the opposite side is gone, so it costs d
- Divide the cost by 2 through flow rate 2 to get what you want to ask for. relevance
- least-cost current
- maximum current
- Comes down to the shortest path problem.
This page is auto-translated from /nishio/最小費用流に帰着 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.