-
Notifications
You must be signed in to change notification settings - Fork 3
/
catvsdog.py
32 lines (30 loc) · 985 Bytes
/
catvsdog.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from random import choice
import sys; input = sys.stdin.readline
def solve():
def aug(l):
if vis[l]: return 0
vis[l] = 1
for r in g[l]:
if match[r] == -1 or aug(match[r]): match[r] = l; return 1
return 0
C, D, v = map(int, input().split())
V = 2*v
g = [[] for _ in range(V)]
match, mcbm = [-1]*V, 0
free = set(range(v))
nfree = len(free)
votes = [input().strip().split() for _ in range(v)]
for i in range(v-1):
for j in range(i+1, v):
if votes[i][0] == votes[j][1] or votes[i][1] == votes[j][0]: g[i].append(j+v), g[j].append(i+v)
for l in list(free):
candidates = [r for r in g[l] if match[r] == -1]
if candidates:
mcbm += 1
free.discard(l)
match[choice(candidates)] = l
for f in free:
vis = [0]*nfree
mcbm += aug(f)
print(v-mcbm//2)
for _ in range(int(input())): solve()