Polyn0mial's blog

By Polyn0mial, 21 month(s) ago, In English

I'm solving ABC 259 pG.

Here's the article that I found.

I can understand "The project selection problem" part, but doesn't know how to modify it. To be clear, if $$$task_i$$$ is dependent on $$$task_j$$$, we simply add an edge from $$$i$$$ to $$$j$$$ with $$$\infty$$$ weight. What if we want a penalty when both $$$i$$$ and $$$j$$$ are chosen? How do we reconstruct the edges? (Actually from the code of leaderboard it seems like we add an edge from $$$i$$$ to $$$j$$$ with $$$penalty$$$ weight, but why? Adding an edge with $$$\infty$$$ weight means we can't cut the edge there, but what if the weight isn't $$$\infty$$$? What does it mean when the cut is in the middle?)

Also, are there more resources that I can read for constructing flows? I've googled it and most of them were talking about flow algorithms instead of flow constructions.

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?