.PEIN.'s blog

Contest On Maximum Flow/ Matching
By .PEIN., 13 years ago, In English

A contest on max flow and matching related algorithms will start within 1 hr. There is be 6 problems. Link: http://lightoj.com/practice_contest_index.php?contest_id=88

EDIT: contest duration has been extended to 24 hrs. You are invited to join. :)

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

»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was unable to understand the statements without some guessing :(. Problem statements contains lots of grammar & vocabulary mistakes (e.g. shouldn't A's title be "Fed Up With Teaching" ?).

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell me how to solve "D — Dark Time for Dark Wizard"? I have used Min-Cost-Max-Flow, but my graph was wrong. The main problem is edges are bidirectional, and we can use them at most once.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Split the edges and run Min-Cost-Max-Flow. By splitting the edges I mean, treat each edge as a different one, insert a new node within the edge for every edge.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please describe it on example, or more precisely. I have added two vertices for each edge, if we have edge between A and B with cost X, my program adds two vertices C and D, and the edges (start, end, cap, cost) : (A, C, 1, X) (B, C, 1, X) (D, A, 1, 0) (D, B, 1, 0) (C, D, 1, 0), but this graph has negative cycles.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Suppose there are two edges between A and B with cost 3 and 5. If you split these two edges with node C, D then it'll look like this, (start, end, cap, cost) : (A, C , 1 , 3), (C, B , 1 , 0), (A, D , 1 , 5), (D, B , 1 , 0). These edges are bidirectional. Now if we run min-cost-max-flow on a bidirectional graph, we'd get maximum amount of death eater each with shortest path to voldemort.

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Are you solved this problem? edges are bidirectional. Your example is wrong, because we have not possibility to go from B to A. Use only one edge (A, B) in your future example please.

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, I've solved the problem. If there was no multiple edges in this problem, this would've been a straight forward min-cost-max-flow solution. Since there can be multiple edges between any two nodes, I've split the edges and ran min-cost-max-flow. If you want I can show you my code.

            → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody write editorial for this contest? That will be great. Thanks.

→ Reply