Page MenuHomec4science
Files F94916797

problemA.py
No OneTemporary
Actions

File Metadata

Created
Wed, Dec 11, 09:26

problemA.py
View Options

#!/usr/bin/python
# Elfi da nord a sud in delivery
# Non si devono incontrare
# n nodes: cities
# m nodes: road linking cities
# 1 = north pole
# n = south pole
# TASK: find maximum number of disjoint paths connecting north pole to south pole
class EnumGraph:
def __init__(self, n, A):
self.n = n
self.A = A
def __len__(self):
return self.n
# run bst starting from the current edge
# path = buffer in which to store the parent of the visited nodes
def explore_unit(self, s, t, path):
# distance counter
visited = [False for i in range(t+1)]
visited[s] = True
Q = [] # bsf queue
Q.append(s)
#print("s = ", s+1)
#print("t = ", t+1)
while len(Q) > 0:
#print("Q = ", Q)
u = Q.pop(0) # dequeue
# from u+1 to t because of increasing path order
for v in range(s,t+1):
#for v in range(u+1,t+1):
# filter u -> v and not visited
if self.A[u][v] and not visited[v]:
#print("From %d, visited %d" % (u+1,v+1))
visited[v] = True
Q.append(v)
# compile path array
path[v] = u
return visited[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(n)] for i in range(n)]
for i in range(m):
line = fstream.readline().split(' ')
a = int(line[0])
b = int(line[1])
A[a-1][b-1] = 1
A[b-1][a-1] = 1
return EnumGraph(n, A)
# ford-kulkerson for a flow with capacity 1
def ford_kulkerson_unit(flow):
f = 0 # initial flow
n = flow.n
if n < 2:
raise Exception("Entering a sinkless flow")
# sum over all connected paths of the source
#remain = sum(flow.A[0])
#total = remain
# path storage
path = [-1 for i in range(n)]
counter = 0
while flow.explore_unit(0, n-1, path):
# a new path was found
counter += 1
# update flow
v = n-1
while v > 0:
u = path[v] # get previous element
flow.A[u][v] = 0 # invert adjacency
flow.A[v][u] = 1
v = u
return counter
"""
while remain > 0:
# find a path and compute residual graph
prec = -1
target = 0
arrived = False
while not arrived:
advanced = False
for nextedge in range(target+1,n):
# skip if not adjacent
if flow.A[target][nextedge] == 0:
continue
# advance in augmenting path
# set the preceiding as the current target
prec = target
# set the target as the destination
target = nextedge
# update target in flow, invert flow direction
flow.A[prec][target] = 0
flow.A[target][prec] = 1
# at last, check if arrived
if target == n-1:
arrived = True
remain -= 1
#print("Found path: %d -> %d " % (prec+1, target+1))
advanced = True
break
if not advanced:
# no other possible cycles
print("Vicolo cieco")
return total - remain
#raise Exception("Path for target %d not found" % (target+1))
return total - remain
"""
import sys
graph = parseinput(sys.stdin)
print(ford_kulkerson_unit(graph))

Event Timeline

c4science · Help