# Part2:作业

• 作业1

05-树7 堆中的路径（25 分）

5 3
46 23 26 24 10
5 4 3

24 23 10
46 23 10
26 10

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 09 12:22:45 2018

@author: 715073608
"""

#定义堆
class Heap():
def __init__(self,x,y):
self.heap=y
self.len=len(y)
#type定义堆类型，x=1表示递增,x=0表示递减
self.type=x

def insert(self,x):
self.heap.append(x)
self.len+=1
i=self.len
if self.type==1:
while (i>=2):
#print self.heap
#不满足递增堆的定义时交换父子
if self.heap[i-1]<self.heap[i/2-1]:
self.heap[i-1],self.heap[i/2-1]=self.heap[i/2-1],self.heap[i-1]
i/=2
else:
break
#print self.heap,'1'
elif self.type==0:
while (i>=2):
#print self.heap
#不满足递减堆的定义时交换父子
if self.heap[i-1]>self.heap[i/2-1]:
self.heap[i-1],self.heap[i/2-1]=self.heap[i/2-1],self.heap[i-1]
i/=2
else:
break

def heaprd(x,i):
a=''
a+=str(x.heap[i-1])
i/=2
while i>0:
a+=' '+str(x.heap[i-1])
i/=2
return a

heap=Heap(1,[])
a=map(int,raw_input().strip().split(' '))
b=map(int,raw_input().strip().split(' '))
c=map(int,raw_input().strip().split(' '))
for i in b:
heap.insert(i)
for i in c:
print heaprd(heap,i)

• 作业2

05-树8 File Transfer（25 分）
We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

### Input Specification:

Each input file contains one test case. For each test case, the first line contains N ($2≤N≤10^4$), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:
I c1 c2
where I stands for inputting a connection between c1 and c2; or
C c1 c2
where C stands for checking if it is possible to transfer files between c1 and c2; or S
where S stands for stopping this case.

### Output Specification:

For each C case, print in one line the word “yes” or “no” if it is possible or impossible to transfer files between c1 and c2, respectively. At the end of each case, print in one line “The network is connected.” if there is a path between any pair of computers; or “There are k components.” where k is the number of connected components in this network.
Sample Input 1:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S
Sample Output 1:
no
no
yes
There are 2 components.
Sample Input 2:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S
Sample Output 2:
no
no
yes
yes
The network is connected.


# -*- coding: utf-8 -*-
"""
Created on Mon Apr 09 13:13:46 2018

@author: 715073608
"""
a=int(raw_input())
b=[]
while True:
temp=raw_input().strip().split(' ')
#print temp
if temp[0]=='S':
break
else:
b.append(temp)

c={}

for i in range(1,a+1):
c[i]=-1

def find(s,x):
if s[x]<0:
return x
else:
s[x]=find(s,s[x])
return s[x]

def union(s,x,y):
root1=find(s,x)
root2=find(s,y)
#print root1,root2
if s[root1]<s[root2]:
s[root1]+=s[root2]
s[root2]=root1
else:
s[root2]+=s[root1]
s[root1]=root2

for i in b:
if i[0]=='I':
union(c,int(i[1]),int(i[2]))
else:
root1=find(c,int(i[1]))
root2=find(c,int(i[2]))
if root1==root2:
print 'yes'
else:
print 'no'
ans=0
for i in c:
if c[i]<0:
ans+=1
if ans==1:
print 'The network is connected.'
else:
print 'There are '+str(ans)+' components.'

• 作业3

05-树9 Huffman Codes（30 分）
In 1953, David A. Huffman published his paper “A Method for the Construction of Minimum-Redundancy Codes”, and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string “aaaxuaxz”, we can observe that the frequencies of the characters ‘a’, ‘x’, ‘u’ and ‘z’ are 4, 2, 1 and 1, respectively. We may either encode the symbols as {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}, or in another way as {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}, both compress the string into 14 bits. Another set of code can be given as {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}, but {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} is NOT correct since “aaaxuaxz” and “aazuaxax” can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.

### Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤63), then followed by a line that contains all the N distinct characters and their frequencies in the following format:
c[1] f[1] c[2] f[2] … c[N] f[N]
where c[i] is a character chosen from {‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}, and f[i] is the frequency of c[i] and is an integer no more than 1000. The next line gives a positive integer M (≤1000), then followed by M student submissions. Each student submission consists of N lines, each in the format:
c[i] code[i]
where c[i] is the i-th character and code[i] is an non-empty string of no more than 63 ‘0’s and ‘1’s.

### Output Specification:

For each test case, print in each line either “Yes” if the student’s submission is correct, or “No” if not.
Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.
Sample Input:
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11
Sample Output:
Yes
Yes
No
No

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 09 21:41:46 2018

"""

'''首先构造哈夫曼树，计算WPL,如果输入的WPL不等于哈夫曼树的WPL，则输出no，否则，判断是否为前缀码

'''

n=int(raw_input())
a=raw_input().strip().split(' ')
b={}
c=[]
for i in range(n):
s=int(a[2*i+1])
b[a[2*i]]=s
c.append(s)

num=int(raw_input())

ans={}
score1={}
#读入
for i in range(num):
temp={}
flag=0
score=0
for j in range(n):
s=raw_input().strip().split(' ')
temp[s[0]]=s[-1]
if len(s[-1])==63:
flag=1
score+=len(s[-1])*b[s[0]]
#temp['flag']=flag
ans[i]=temp
score1[i]=(score,flag)

'''
n=7
b={'A': 1, 'B': 1, 'C': 1, 'D': 3, 'E': 3, 'F': 6, 'G': 6}
c=[1,1,1,3,3,6,6]
d={'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0}
num=4
ans={0: {'A': '00000', 'B': '00001', 'C': '0001', 'D': '001', 'E': '01', 'F': '10', 'G': '11',},
1: {'A': '01010', 'B': '01011', 'C': '0100', 'D': '011', 'E': '10', 'F': '11', 'G': '00'},
2: {'A': '000', 'B': '001', 'C': '010', 'D': '011', 'E': '100', 'F': '101', 'G': '110'},
3: {'A': '00000', 'B': '00001', 'C': '0001', 'D': '001', 'E': '00', 'F': '10', 'G': '11'}}
'''
'''
n=3
b={'A':1,'B':2,'C':3}
c=[1,2,3]
d={'A':0,'B':0,'C':0}
num=2
ans={0:{'A':'10','B':'11','C':'0'},
1:{'A':'10','B':'11','C':'1'}}
'''

#判断是否有歧义
def qz(x):
for i in x:
for j in x:
if i!=j:
if isqz(x[i],x[j])==0:
return 0
return 1

#定义最小堆
class Heap(object):
#初始化,a为哨兵
def __init__(self,x,a,M):
#哨兵填入首元素
s=[a]
s+=x
self.data=s
self.len=len(x)
self.size=M

#将以第self.data[p]为根的子堆调整为最小堆
def PerDown(self,p):
#print self.data[p:],1
x=self.data[p]
parent=p
while(parent<=self.len/2):
child=2*parent
#print child,parent
#将child指向子节点中较小的值
if (child<self.len and (self.data[child]>self.data[child+1])):
child+=1
if(x<=self.data[child]):
break
else:
self.data[parent]=self.data[child]
parent=child
self.data[parent]=x
#print self.data[p:],2

def BuildHeap(self):
i=self.len
while(i>0):
#print self.data,i
self.PerDown(i)
#print self.data
i-=1

#插入元素
def insert(self,x):
if self.len==self.size:
print('已满')
#return False
else:
self.data.append(x)
self.len+=1
i=self.len
while(self.data[i/2]>x):
self.data[i]=self.data[i/2]
i/=2
self.data[i]=x
#return True

#抛出最小元素
def extract(self):
if self.len==0:
print("堆为空")
else:
start=self.data[1]
#从最后一个元素开始，找到小于
x=self.data[-1]
self.len-=1
parent=1
while(parent*2<=self.len):
child=2*parent
#将child指向子节点中较小的值
if (child<self.len and (self.data[child]>self.data[child+1])):
child+=1
if(x<=self.data[child]):
break
else:
self.data[parent]=self.data[child]
parent=child
self.data[parent]=x
del self.data[-1]
return start

#利用之前的结论计算WPL
def Huffman(x):
s=0
while x.len>1:
l=x.extract()
r=x.extract()
s+=l+r
x.insert(l+r)
return s
heap=Heap(c,0,10000)
heap.BuildHeap()
#print heap.data
#score=Huffman(heap,b.copy())
score=Huffman(heap)

def huffsum(x,y):
s=0
for i in x:
s+=len(x[i])*y[i]
return s

for i in range(num):
if score1[i][0]==score and qz(ans[i]):
print 'Yes'
else:
print 'No'