Superbull Python

USACO 2015 February Silver Problem 3¶

Superbull¶

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

In [1]:

# compute edge weights for example data
N = 4
ID = [3,6,9,10]
for t1 in ID:
    for t2 in ID:
        if(t1<t2):
            print(t1,t2,t1^t2)
        

3 6 5
3 9 10
3 10 9
6 9 15
6 10 12
9 10 3

In [2]:

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

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

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
    
    for k in range(N):
        W[k] = max(W[k], ID[nextNode] ^ ID[k])
        
print("\nMax weight spanning tree:",result)

[3, 6, 9, 10]

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

Max weight spanning tree: 37