Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- INF = 1000000
- class Dinic:
- def __init__(self, n):
- self.lvl = [0] * n
- self.ptr = [0] * n
- self.q = [0] * n
- self.adj = [[] for _ in xrange(n)]
- def add_edge(self, a, b, c, rcap=0):
- self.adj[a].append([b, len(self.adj[b]), c, 0])
- self.adj[b].append([a, len(self.adj[a]) - 1, rcap, 0])
- def dfs(self, v, t, f):
- if v == t or not f:
- return f
- for i in xrange(self.ptr[v], len(self.adj[v])):
- e = self.adj[v][i]
- if self.lvl[e[0]] == self.lvl[v] + 1:
- p = self.dfs(e[0], t, min(f, e[2] - e[3]))
- if p:
- self.adj[v][i][3] += p
- self.adj[e[0]][e[1]][3] -= p
- return p
- return 0
- def calc(self, s, t):
- flow, self.q[0] = 0, s
- for l in xrange(31):
- while True:
- self.lvl, self.ptr = [0] * len(self.q), [0] * len(self.q)
- qi, qe, self.lvl[s] = 0, 1, 1
- while qi < qe and not self.lvl[t]:
- v = self.q[qi]
- qi += 1
- for e in self.adj[v]:
- if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
- self.q[qe] = e[0]
- qe += 1
- self.lvl[e[0]] = self.lvl[v] + 1
- p = self.dfs(s, t, INF)
- while p:
- flow += p
- p = self.dfs(s, t, INF)
- if not self.lvl[t]:
- break
- return flow
- while True:
- n, m, g = map(int, raw_input().split())
- if n == 0:
- break
- ar = [[(m) for _ in xrange(n)] for __ in xrange(n)]
- s = n + (n * n) + 3
- t = n + (n * n) + 4
- flow = Dinic(t + 1)
- pontos = [[0, (n-1) * m] for _ in xrange(n)]
- #print pontos
- for k in xrange(g):
- a, r, b = raw_input().split()
- a = int(a)
- b = int(b)
- if r == "=":
- pontos[a][0] += 1
- pontos[b][0] += 1
- elif r == "<":
- pontos[a][0] += 0
- pontos[b][0] += 2
- else:
- pontos[b][0] += 0
- pontos[a][0] += 2
- ar[a][b] -= 1
- ar[b][a] -= 1
- pontos[a][1] -= 1
- pontos[b][1] -= 1
- soma = 0
- for k in xrange(n):
- soma += pontos[k][1]
- win = pontos[0][0] + (pontos[0][1] * 2)
- qtd_j = (soma/2) - pontos[0][1]
- #print qtd_j
- #print win
- #print pontos
- for k in xrange(1, n):
- flow.add_edge(s, k, min((pontos[k][1] - ar[0][k])* 2, max(win - pontos[k][0] -1, 0)))
- at = n + 1
- for k in xrange(1, n):
- for i in xrange(k + 1, n):
- if ar[k][i] > 0:
- flow.add_edge(i, at, 2)
- flow.add_edge(k, at, 2)
- flow.add_edge(at, t, 2 * ar[k][i])
- at += 1
- fluxo = flow.calc(s, t)
- #print fluxo
- if qtd_j * 2 == fluxo:
- print "Y"
- else:
- print "N"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement