Advertisement
Guest User

Untitled

a guest
Sep 20th, 2019
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.39 KB | None | 0 0
  1. INF = 1000000
  2.  
  3. class Dinic:
  4. def __init__(self, n):
  5. self.lvl = [0] * n
  6. self.ptr = [0] * n
  7. self.q = [0] * n
  8. self.adj = [[] for _ in xrange(n)]
  9.  
  10. def add_edge(self, a, b, c, rcap=0):
  11. self.adj[a].append([b, len(self.adj[b]), c, 0])
  12. self.adj[b].append([a, len(self.adj[a]) - 1, rcap, 0])
  13.  
  14. def dfs(self, v, t, f):
  15. if v == t or not f:
  16. return f
  17.  
  18. for i in xrange(self.ptr[v], len(self.adj[v])):
  19. e = self.adj[v][i]
  20. if self.lvl[e[0]] == self.lvl[v] + 1:
  21. p = self.dfs(e[0], t, min(f, e[2] - e[3]))
  22. if p:
  23. self.adj[v][i][3] += p
  24. self.adj[e[0]][e[1]][3] -= p
  25. return p
  26.  
  27. return 0
  28.  
  29. def calc(self, s, t):
  30. flow, self.q[0] = 0, s
  31. for l in xrange(31):
  32. while True:
  33. self.lvl, self.ptr = [0] * len(self.q), [0] * len(self.q)
  34. qi, qe, self.lvl[s] = 0, 1, 1
  35. while qi < qe and not self.lvl[t]:
  36. v = self.q[qi]
  37. qi += 1
  38. for e in self.adj[v]:
  39. if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
  40. self.q[qe] = e[0]
  41. qe += 1
  42. self.lvl[e[0]] = self.lvl[v] + 1
  43.  
  44. p = self.dfs(s, t, INF)
  45. while p:
  46. flow += p
  47. p = self.dfs(s, t, INF)
  48.  
  49. if not self.lvl[t]:
  50. break
  51.  
  52. return flow
  53.  
  54. while True:
  55. n, m, g = map(int, raw_input().split())
  56. if n == 0:
  57. break
  58. ar = [[(m) for _ in xrange(n)] for __ in xrange(n)]
  59. s = n + (n * n) + 3
  60. t = n + (n * n) + 4
  61. flow = Dinic(t + 1)
  62. pontos = [[0, (n-1) * m] for _ in xrange(n)]
  63.  
  64. #print pontos
  65. for k in xrange(g):
  66. a, r, b = raw_input().split()
  67. a = int(a)
  68. b = int(b)
  69. if r == "=":
  70. pontos[a][0] += 1
  71. pontos[b][0] += 1
  72. elif r == "<":
  73. pontos[a][0] += 0
  74. pontos[b][0] += 2
  75. else:
  76. pontos[b][0] += 0
  77. pontos[a][0] += 2
  78.  
  79. ar[a][b] -= 1
  80. ar[b][a] -= 1
  81. pontos[a][1] -= 1
  82. pontos[b][1] -= 1
  83. soma = 0
  84. for k in xrange(n):
  85. soma += pontos[k][1]
  86.  
  87. win = pontos[0][0] + (pontos[0][1] * 2)
  88. qtd_j = (soma/2) - pontos[0][1]
  89. #print qtd_j
  90. #print win
  91. #print pontos
  92. for k in xrange(1, n):
  93. flow.add_edge(s, k, min((pontos[k][1] - ar[0][k])* 2, max(win - pontos[k][0] -1, 0)))
  94.  
  95. at = n + 1
  96. for k in xrange(1, n):
  97. for i in xrange(k + 1, n):
  98. if ar[k][i] > 0:
  99. flow.add_edge(i, at, 2)
  100. flow.add_edge(k, at, 2)
  101. flow.add_edge(at, t, 2 * ar[k][i])
  102. at += 1
  103. fluxo = flow.calc(s, t)
  104. #print fluxo
  105. if qtd_j * 2 == fluxo:
  106. print "Y"
  107. else:
  108. print "N"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement