Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F94914246
bridge_copy.py
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Wed, Dec 11, 08:54
Size
3 KB
Mime Type
text/x-python
Expires
Fri, Dec 13, 08:54 (2 d)
Engine
blob
Format
Raw Data
Handle
22898906
Attached To
rMARAFFO Master-cycle
bridge_copy.py
View Options
#!/usr/bin/python
class
LkList
:
def
__init__
(
self
,
x
,
_prev
,
_next
):
self
.
x
=
x
self
.
_prev
=
_prev
self
.
_next
=
_next
class
Queue
:
def
__init__
(
self
):
self
.
head
=
None
self
.
tail
=
None
self
.
N
=
0
def
enqueue
(
self
,
x
):
if
self
.
head
is
not
None
:
self
.
head
.
_prev
=
LkList
(
x
,
None
,
self
.
head
)
self
.
head
=
self
.
head
.
_prev
else
:
self
.
head
=
LkList
(
x
,
None
,
None
)
self
.
tail
=
self
.
head
self
.
N
+=
1
def
dequeue
(
self
):
if
self
.
tail
is
None
:
return
None
else
:
x
=
self
.
tail
.
x
if
self
.
tail
.
_prev
is
not
None
:
self
.
tail
.
_prev
.
_next
=
None
else
:
self
.
head
=
None
self
.
tail
=
self
.
tail
.
_prev
self
.
N
-=
1
return
x
def
__len__
(
self
):
return
self
.
N
class
Flow
:
def
__init__
(
self
,
N
,
A
,
s
=
-
1
,
t
=
-
1
):
self
.
s
=
0
if
s
<
0
else
s
self
.
t
=
N
-
1
if
t
<
0
else
t
self
.
N
=
N
self
.
A
=
A
def
__len__
(
self
):
return
self
.
N
# run bfs starting from source
# path = buffer in which to store the parent of the visited nodes
def
find_augmenting_path
(
self
,
path
):
# distance counter
visited
=
[
False
for
i
in
range
(
self
.
N
)]
visited
[
self
.
s
]
=
True
Q
=
Queue
()
# bsf queue
Q
.
enqueue
(
self
.
s
)
while
len
(
Q
)
>
0
:
u
=
Q
.
dequeue
()
# dequeue
for
v
in
range
(
self
.
N
):
# filter u -> v and not visited
if
self
.
A
[
u
][
v
]
>
0
and
not
visited
[
v
]:
#print("From %d, visited %d" % (u+1,v+1))
visited
[
v
]
=
True
Q
.
enqueue
(
v
)
# compile path array
path
[
v
]
=
u
return
visited
[
self
.
t
]
def
parseinput
(
fstream
):
line
=
fstream
.
readline
()
.
split
(
' '
)
n
=
int
(
line
[
0
])
# number of nodes
m
=
int
(
line
[
1
])
# number of edges
# Setup Adj matrix
A
=
[[
0
for
i
in
range
(
2
*
n
+
2
)]
for
i
in
range
(
2
*
n
+
2
)]
# layout:
# i = 0 -> source
# i = 1,...,n -> island A
# i = n + 1, ..., 2n -> island B
# i = 2n + 1 -> sink
# assign bridges
for
i
in
range
(
m
):
line
=
fstream
.
readline
()
.
split
(
' '
)
a
=
int
(
line
[
0
])
b
=
int
(
line
[
1
])
+
n
A
[
a
][
b
]
=
1
A
[
b
][
a
]
=
1
# assign source and sink
for
i
in
range
(
1
,
n
+
1
):
A
[
0
][
i
]
=
2
A
[
i
][
0
]
=
2
A
[
2
*
n
+
1
][
n
+
i
]
=
2
A
[
n
+
i
][
2
*
n
+
1
]
=
2
return
Flow
(
2
*
n
+
2
,
A
)
# ford-kulkerson for a flow s.t. for all paths from s to t : min capacity = 1
def
ford_kulkerson_unit
(
flow
):
n
=
flow
.
N
if
n
<
2
:
raise
Exception
(
"Entering a sinkless flow"
)
# paths memorization
P
=
[]
# path storage
path
=
[
-
1
for
i
in
range
(
n
)]
while
flow
.
find_augmenting_path
(
path
):
# update flow
# Warning: suppose that min capacity is 1, not the general case
# Notice: max-flow = len(P)
v
=
n
-
1
while
v
>
0
:
u
=
path
[
v
]
# get parent vertex
flow
.
A
[
u
][
v
]
-=
1
# decrease capacity on residual graph
flow
.
A
[
v
][
u
]
+=
1
# increase capacity on residual graph
v
=
u
P
.
append
(
path
)
return
len
(
P
)
import
sys
graph
=
parseinput
(
sys
.
stdin
)
print
(
ford_kulkerson_unit
(
graph
))
Event Timeline
Log In to Comment