RestingRajarshi's blog

Help in China — NOI problem
By RestingRajarshi, 5 years ago, In English

I was looking at this NOI problem from another CF post.

Apparently there is a network flow solution to it, but i don't get how it works. Can someone explain in a bit more details? I am not too experienced in flows. Would be a great help.

(PS: I got the LP constraints. If that is important.)

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

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

Simplex-Algorithm and Dual-Rule work on this problem.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Is simplex possible to be implemented in an OI style contest in 5hrs?

    Plus i got that. I wanted the flow solution/explaination.

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

      I can't explain the method clearly. So..https://paste.ubuntu.com/p/t9h93pxttD/

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

        (a,b) represents an edge with capacity a and cost b

        My modeling method: for day I, I connects to I +1 (inf-a[I],0); For the i-type volunteers, s[I] connects to t[I]+1 (inf,c[I]).

        Super source is day 1, super sink is day N+2, day N+1 connects edge to day N+2 (inf,0), the maximum flow is obviously inf, and the minimum cost is the answer we require

        If you draw this on paper, you can see that for any given day, the traffic is inf. Since we subtracted a[I] from the edge between the two days, we got no less than a[I] by "hiring volunteers".

        来自有道翻译，原文： (a,b)表示一条容量为a费用为b的边 我的建模方式：对于第i天，i向i+1连边(inf-a[i],0)；对于第i种志愿者，s[i]向t[i]+1连边(inf,c[i]) 超级源为第1天，超级汇为第N+2天，第N+1天向第N+2天连边(inf,0)，最大流显然为inf，最小费用就是我们要求的答案 将这个图画在纸上，你可以发现对于任意一天，它的流量均为inf。由于我们在两天之间的连边减去了a[i]，所以通过“雇佣志愿者”得到的流量不小于a[i]

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The Simplex method solution: https://paste.ubuntu.com/p/vQtWSxvG92/

      → Reply