# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
8 | ecnerwala | 3494 |
9 | Um_nik | 3396 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 164 |
2 | Um_nik | 163 |
3 | atcoder_official | 159 |
4 | cry | 158 |
5 | -is-this-fft- | 157 |
6 | adamant | 155 |
6 | awoo | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | Dominater069 | 152 |
Name |
---|
Simplex-Algorithm and Dual-Rule work on this problem.
Is simplex possible to be implemented in an OI style contest in 5hrs?
Plus i got that. I wanted the flow solution/explaination.
I can't explain the method clearly. So..https://paste.ubuntu.com/p/t9h93pxttD/
(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]
The Simplex method solution: https://paste.ubuntu.com/p/vQtWSxvG92/