USACO SuperBull / Prim's Algorithm

USACO 2015 February Silver Problem 3¶

Superbull, solved with Prim's Algorithm¶

http://usaco.org/index.php?page=viewproblem2&cpid=531

In [1]:

# SAMPLE INPUT:
#
#
# 4
# 3
# 6
# 9
# 10

In [2]:

fin = open ('superbull.in', 'r')
fout = open ('superbull.out', 'w')
N = int(fin.readline().strip())
ID = []
for i in range(N):
    ident = int(fin.readline().strip())
    ID.append(ident)
  
print("team1","team2","score")
for t1 in ID:
    for t2 in ID:
        if(t1<t2):
            print(t1,t2,t1^t2)

team1 team2 score
3 6 5
3 9 10
3 10 9
6 9 15
6 10 12
9 10 3

In [3]:

result = 0
used = [False]*N
W = [0]*N
print("\nStart node:",ID[0])

# score the edges coming out of the zeroth node
used[0] = True
for k in range(1,N):
    W[k] = max(W[k], ID[0] ^ ID[k]) 

Start node: 3

In [4]:

for counter in range(N-1):
    # Find nextNode, with max edge weight from the current spanning tree. 
    nextNode = -1
    for trialNode in range(N):
        if (used[trialNode]):
            continue
        if (nextNode == -1 or W[trialNode] > W[nextNode]): 
            nextNode = trialNode
            
    # Update the result and score the edges coming out of nextNode.
    print("Add node:",ID[nextNode],"Edge weight:",W[nextNode])
    result += W[nextNode]
    used[nextNode] = True
    
    # list W[k] contains the maximum weight edge going from used nodes to the kth node
    for k in range(N):
        W[k] = max(W[k], ID[nextNode] ^ ID[k])
        
print("\nMax weight spanning tree:",result)

Add node: 9 Edge weight: 10
Add node: 6 Edge weight: 15
Add node: 10 Edge weight: 12

Max weight spanning tree: 37

In [5]:

fout.write(str(result)+"\n")
fout.close()