965 - Police Road Blocks

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
xtof.durr
New poster
Posts: 1
Joined: Mon Jun 16, 2008 4:26 pm

965 - Police Road Blocks

Post by xtof.durr » Thu Jun 19, 2008 10:30 am

Does someone know if the graph is planar. Without any particular promise on the input there is no way to solve it in linear time.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 965 - Police Road Blocks

Post by brianfry713 » Thu May 15, 2014 10:30 pm

I created a dataset and emailed it to the admins.

I did not test whether the input graph is planar. I solved it using Edmonds–Karp algorithm.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 9 (900-999)”