|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | MaxFlow | Fetisov Alex [Psych Up club] | 1664. Нефтепроводы | 31 май 2018 16:03 | 3 | MaxFlow Fetisov Alex [Psych Up club] 17 окт 2013 04:16 Did anybody get AC with the MaxFlow algorithm? Re: MaxFlow Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 17 окт 2013 10:48 Push relabel algorithm got TL on test 30.
Dinic with scaling got AC in 0.249 s.
Interestingly, push-relabel algorithm (with some optimizations) that I used is usually a little bit faster than my Dinic with scaling. | | What is the output for this test case? | The Usual Suspect | 1664. Нефтепроводы | 12 окт 2016 05:53 | 1 | 6
0 0
5 -10
10 -10
5 -5
10 -5
20 0
7
1 2 10
2 3 30
3 5 20
5 4 20
4 2 20
3 6 10
1 6 7
ans:
17
1 2 10
2 3 30
3 5 20
5 4 20
4 2 20
3 6 10
1 6 7
Is this output acceptable? Or do we have to remove flow cycles?
update: got ac without removing cycles.
Edited by author 13.10.2016 06:41 | | what are the coordinates for? | LSBG | 1664. Нефтепроводы | 19 дек 2011 12:08 | 9 | I can't understand what do we need the plain coordinates for.
Edited by author 20.12.2008 14:48 For nothing I think.
I absolutely ignored coords, used standard Maxflow and got TLe13 because of 0.5 sec. Main point is speed. There are 2 different ways to solve this problem. The first one is to optimize one of the standard Maxflow algorithms to pass TL. The second one is to use the planarity of graph, design an algorithm that is asymptotically faster than the standard ones, and get AC with it. I wrote this problem one year before , with standart maxflow algorithm , and got AC during the contest. Exuse me!.Brilliant the problem, thank the authors.
We build dual graph and use Dejkstra in it- O(nlog(n)).
But computing dual graph is separated difficult problem
from computational geometry connected with walking on grid
with extacting faces.
Now I am implementing this approach.
In test 14 I have situation when starting from some
edge and making maximal possible turn to left we don't
return to starting edge. Is it possible in
comlex geometry or bug in program.
Edited by author 18.07.2009 11:05 I've implemented svr's approach and it seems to be the fastest one.
I had a lot of problems with my program, but not on test 14 or 15.
But I have overcome WA#16 when replaced atan2 with exact geometry. Found: test 14 contains edge with only one facet :) I also have implemented it.
Dual graph making is not very easy.
But strength (n*log(n)) of this method is great.
I used set,vector and had not TL.
Edited by author 19.12.2011 12:22 | | Which max flow algorithm must be used for acceptable perfomance? | indy256 | 1664. Нефтепроводы | 27 май 2011 06:52 | 4 | Does Dinic need some optimisation? It is O(n^2 * m) algorithm. This complexity is too large for 10^4 vertexes and 3*10^4 edges. You should use as few variables as you can , in your dfs procedure. It does save time.
And you should 'delete' useless edges(which you've augmented it).
That's all measures I used in my dinic. And I got accepted within the limit.But still not too good.
Edited by author 27.05.2011 06:52 | | Test Case Issue | Varun Kumar(Fundu) | 1664. Нефтепроводы | 14 июл 2009 12:26 | 2 | Hi,
for Test Case
4
0 0
1 1
3 3
5 5
5
1 2 500
1 3 50
2 3 100
2 4 200
3 4 120
Answer could be:
320
1 2 300
1 3 20
2 3 100
2 4 200
3 4 120
or
320
1 2 270
1 3 50
2 3 70
2 4 200
3 4 120
which one is correct?
could any provide some more test cases??
| | Time | [ksu] glTron::teal | 1664. Нефтепроводы | 2 фев 2009 12:13 | 5 | Time [ksu] glTron::teal 20 дек 2008 16:28 We have 10 000 station. And we have M<=100 000 000 pipelines between station. And we have only 0.5 seconds fo read 300 000 000 numbers. It is not possible!!!
Judges must do something with this problem! There are much less than 300000000 pipelines. The graph is flat. Flat graph with N vertices can have maximum 2*N-3 edges, so the problem input is not so large Flat graph with N>2 vertices can have maximum 3*N-6 edges! Oops... You are right! :) |
|
|
|
