[UVa] 10080 - Gopher II

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10080 - Gopher II
Source            : UVa Online Judge
Category          : Graph Theory
Algorithm         : Maximum Bipartite Matching, Maximum Independent Set
Verdict           : Accepted

import math
 
def read():
    return map(int, input().split())
 
def readAll():
    return (int(i) for i in input().split())
 
maxn = 500 + 5
 
graph = [[] for _ in range(maxn)]
 
def addEdge(u, v):
    graph[u].append(v)
    graph[v].append(u)
 
Left = [0]*maxn
Right = [0]*maxn
seen = [0]*maxn
 
def kuhn(u):
    seen[u] = True
    for v in graph[u]:
        if seen[v] is True:
            continue
        seen[v] = True
        if Right[v] == -1 or kuhn(Right[v]):
            Left[u] = v
            Right[v] = u
            return True
    return False
 
def bpm(n):
    for i in range(maxn):
        Left[i] = Right[i] = -1
    match = 0
    for i in range(1, n+1):
        for j in range(maxn):
            seen[j] = 0
        if kuhn(i) is True:
            match += 1
    return match
 
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def dist(self, p):
        x = abs(self.x - p.x)
        y = abs(self.y - p.y)
        return math.sqrt(x*x + y*y)
 
if __name__ == '__main__':
    while True:
        try:
            n, m, s, v = readAll()
        except:
            break
        vs = s * v * 1.0
        gophers = [Point(0, 0) for _ in range(maxn)]
        holes = [Point(0, 0) for _ in range(maxn)]
        for i in range(1, n+1):
            gophers[i].x, gophers[i].y = map(float, input().split())
        for i in range(1, m+1):
            holes[i].x, holes[i].y = map(float, input().split())
        for i in range(1, n+1):
            for j in range(1, m+1):
                d = gophers[i].dist(holes[j])
                if d <= vs:
                    addEdge(i, j+n)
        match = bpm(n);
        ans = n - match
        print(ans)
        for i in range (maxn):
            graph[i].clear()