CCC '17 S4 - Minimum Cost Flow - DMOJ: Modern Online Judge

CCC '17 S4 - Minimum Cost Flow

Points: 17 (partial)

Time limit: 1.4s

Memory limit: 256M

Author:

Problem type

Canadian Computing Competition: 2017 Stage 1, Senior #4

The city of Watermoo has buildings numbered $1, 2, \dots, N$ $1, 2, \dots, N$ . The city has $M$ $M$ pipes that connect pairs of buildings. Due to urban planning oversights, building $1$ $1$ is the only sewage treatment plant in the city. Each pipe can be either active or inactive. The set of active pipes forms a valid plan if building $1$ $1$ is directly or indirectly connected to each other building using active pipes. (Pipes directly connect pairs of buildings. Buildings $X$ $X$ and $Z$ $Z$ are indirectly connected if $X$ $X$ is directly or indirectly connected to $Y$ $Y$ , and $Y$ $Y$ is directly or indirectly connected to $Z$ $Z$ .)

The municipal government of Watermoo is currently operating a valid plan of $N-1$ $N - 1$ pipes today, but they think it is too expensive! Each pipe has a monthly maintenance fee that the city must pay when it is active, and the total cost of a valid plan is the sum of the maintenance fees of its active pipes. (Inactive pipes cost nothing.)

Additionally, researchers at the University of Watermoo have developed an experimental pipe enhancer which you can use on one pipe of your choice. It will reduce that pipe's cost from $C$ $C$ down to $\max(0, C-D)$ $max (0, C - D)$ , where $D$ $D$ is the enhancer's strength.

The city wants you to minimize the cost of the plan, and they want you to do it quickly. Every day, the city will allow you to activate one pipe, and deactivate another pipe. How many days do you need to make the set of active pipes form a valid plan, whose cost is minimum among all valid plans and all choices of enhanced pipe?

Note that it is possible that the plan becomes invalid while you are working, but by the end it should be a valid plan.

Input Specification

The first line will contain the integers $N$ $N$ , $M$ $M$ , and $D$ $D$ $(1 \le N \le 100\,000, N-1 \le M \le 200\,000, 0 \le D \le 10^9)$ $(1 \leq N \leq 100 000, N - 1 \leq M \leq 200 000, 0 \leq D \leq 10^{9})$ . Each of the next $M$ $M$ lines contain three integers $A_i$ $A_{i}$ , $B_i$ $B_{i}$ , and $C_i$ $C_{i}$ , which means that there is a pipe from building $A_i$ $A_{i}$ to building $B_i$ $B_{i}$ that costs $C_i$ $C_{i}$ per month when activated $(1 \le A_i, B_i \le N, 1 \le C_i \le 10^9)$ $(1 \leq A_{i}, B_{i} \leq N, 1 \leq C_{i} \leq 10^{9})$ . The first $N-1$ $N - 1$ of these lines represent the valid plan the city is currently using.

It is guaranteed that there is at most one pipe connecting any two buildings and no pipe connects a building to itself.

For 3 of the 17 available marks, $N \le 8$ $N \leq 8$ , $M \le 28$ $M \leq 28$ and $D = 0$ $D = 0$ .
For an additional 5 of the 17 available marks, $N \le 1\,000$ $N \leq 1 000$ and $M \le 5\,000$ $M \leq 5 000$ and $D = 0$ $D = 0$ .
For an additional 3 of the 17 available marks, $D = 0$ $D = 0$ .
For an additional 2 of the 17 available marks, $N \le 1\,000$ $N \leq 1 000$ and $M \le 5\,000$ $M \leq 5 000$ .

Note: The final 2 of the 17 available marks consists of test cases made by d and r3mark and were not present on the CCC. These test cases were made in response to the initial incorrect official solution presented.

Output Specification

Output one integer on a single line, the minimum number of days to complete this task. If the initial valid plan is already an optimal plan, then output $0$ $0$ .

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample Output 1

Note that it does not matter which pipe you use the pipe enhancer on because $D = 0$ $D = 0$ , so it will not affect the maintenance fee of any pipe.
On the first day, you should deactivate the pipe from building $2$ $2$ to $3$ $3$ and activate the pipe from building $4$ $4$ to $1$ $1$ .

Sample Input 2

Copy

Sample Output 2

Copy

Explanation for Sample Output 2

One solution using the minimum number of days is to first use the pipe enhancer on the pipe from building $1$ $1$ to $2$ $2$ to decrease its cost to $3$ $3$ . Then on the first day, replace the pipe from building $2$ $2$ to $3$ $3$ with the pipe from building $1$ $1$ to $3$ $3$ , and on the second day replace the pipe from $1$ $1$ to $4$ $4$ with the pipe from building $1$ $1$ to $5$ $5$ . Note that the cost of the optimal plan is $10$ $10$ .
Additionally, there are no solutions where you use the pipe enhancer on the pipe from building $1$ $1$ to $3$ $3$ or the pipe from building $1$ $1$ to $5$ $5$ . Doing so would make that pipe have a maintenance fee of $0$ $0$ , and then any optimal plan would have cost $11$ $11$ (and we have already seen that we can achieve a cost of $10$ $10$ ).

Sample Input 3

Copy

4 4 0
1 2 715827882
2 3 715827882
3 4 715827882
4 1 715827884

Sample Output 3

Copy

Explanation for Sample Output 3

The initial valid plan is already an optimal plan. Be careful of integer overflow when implementing your solution.

Comments

3

Mystical commented on May 14, 2022, 3:16 a.m.

Can Prim's be used to solve this?

-1

zhenga1 commented on Feb. 13, 2021, 12:55 p.m.

Is DFS fast enough to pass?(for python or c++)

-5

dxke02 commented on Feb. 13, 2021, 2:13 p.m. ← edited →

why would you need DFS, this is a minimum spanning tree problem..

https://en.wikipedia.org/wiki/Minimum_spanning_tree#:~:text=A%20minimum%20spanning%20tree%20(MST,minimum%20possible%20total%20edge%20weight.&text=There%20are%20quite%20a%20few%20use%20cases%20for%20minimum%20spanning%20trees.

This comment is hidden due to too much negative feedback. Show it anyway.

0

zhenga1 commented on Feb. 13, 2021, 3:14 p.m.

To find the cycles when doing kruskals. I did DFS and getting TLE on the last few test cases.

3

dxke02 commented on Feb. 13, 2021, 3:29 p.m.

When doing Kruskals, DFS is not needed to detect cycles, the Disjoint-Set data structure is more efficient.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure#:~:text=In%20computer%20science%2C%20a%20disjoint,a%20set%20into%20disjoint%20subsets.

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

26

AlanL commented on Dec. 5, 2018, 1:17 a.m.

CopyPastingFromGithubIsWrong just because this is your username I don't think you can use the editorial ... https://dmoj.ca/src/1117801 and I don't think "just seeing if it works" is a valid reason to use it. I'm pretty sure it would work since it's the editorial???

3

jorgebean commented on March 15, 2022, 5:39 a.m.

I agree, copying code is an egregious crime - I can't believe anyone would so such a thing...

-1

hezeyu2007 commented on April 22, 2018, 5:51 p.m.

If you only use the pipe enhancer, then does it still count as a day?

-5

Xue_Alex commented on July 3, 2017, 12:35 a.m. ← edit 3 →

In the first sample output description it states that the edge between nodes 1 to 4 are activated on the first day. Does that mean the edges aren't activated from day 0, or does it just state that for clarity?

EDIT: I can't read: "The first N−1 of these lines represent the valid plan the city is currently using."

This comment is hidden due to too much negative feedback. Show it anyway.

-1

septence123 commented on March 7, 2017, 7:24 p.m.

Help on last sample case. How is it a valid plan for the last sample case? Doesnt the pipe from 4 to 1 need to be removed?

7

Kirito commented on March 7, 2017, 8:22 p.m.

The first $N-1$ $N - 1$ of these lines represent the valid plan the city is currently using.

As you can see, the first three form a perfectly valid plan.

32

Kirito commented on March 3, 2017, 3:10 a.m. ← edit 2 →

New cases by d and r3mark have been added as a 2 point subtask. All submissions have been rejudged.

-63

root commented on June 17, 2017, 9:30 p.m. ← edited →

A new cases

A new case

New cases

Took two WAs before Kirito got their grammar straight.

Literally laughed out loud

This comment is hidden due to too much negative feedback. Show it anyway.

24

Kirito commented on June 17, 2017, 9:42 p.m.

A new case by d has been added as a 1 point subtask. All submissions have been rejudged.

New cases by d and r3mark have been added as a 2 point subtask. All submissions have been rejudged.

The second edit is because the number of cases increased from 1

-38

AlanCCCL2S18 commented on Dec. 2, 2018, 4:15 p.m.

But still there was "a new cases" which is not grammatically correct under any circumstance.

This comment is hidden due to too much negative feedback. Show it anyway.

36

Xyene commented on Dec. 5, 2018, 2:03 a.m.

Guys, this post is from over a year ago... don't beat a dead horse.