# Part1:回顾

## 1.最小生成树

1. Prime算法
Prime算法是让一颗小数长大。具体思路是先任取一个点a包括在树中，选取距离树中顶点距离最短的边，然后将这个边及对应顶点b包括在树中，更新不在树中的点距离树的最短距离，接来下重复此操作即可。注意由于只增加了点b，所以在更新最短距离的时候只要更新b的相邻点即可。可以看到，这个算法和之前讲的Dijkstra算法很相似，下面一起列出。
2. Kruskal算法
Kruskal算法是每次选取最小权重的边，如果加入此边不形成回路，则将边及顶点加入生成树中。在此过程中，判断是否形成回的方法是使用并查集，每次选取权重最小的边使用最小堆。

# Part2:作业

• 作业1

08-图7 公路村村通（30 分）

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

12

# -*- coding: utf-8 -*-
"""
Created on Wed May 02 10:07:23 2018

"""
n,m=map(int,raw_input().split(' '))

#读入边
index=[]
length=[]
for i in range(m):
a,b,c=map(int,raw_input().split(' '))
length.append(c)
index.append((a,b))

#初始化点
v=[-1 for i in range(n)]

#定义并查集
def find(s,x):
if s[x]<0:
return x
else:
return find(s,s[x])

#定义union,x1,x2为根节点
def union(s,x1,x2):
if s[x1]<s[x2]:
s[x1]+=s[x2]
s[x2]=x1
else:
s[x2]+=s[x1]
s[x1]=x2

#定义判断cycle
def cycle(s,x1,x2):
v1=find(s,x1)
v2=find(s,x2)
return v1,v2

#定义已访问的个数
num=0
#mst边长
l=0

while(num<n and len(length)>0):
#找到最短边
lmin=min(length)
#找到最短边的索引
i=length.index(lmin)
del length[i]
#找到最短边对应的点
edge=index.pop(i)
#判断是否循环，根节点相同表示已联通
x1,x2=cycle(v,edge[0]-1,edge[1]-1)
if x1!=x2:
union(v,x1,x2)
l+=lmin
if num==0:
num+=2
else:
num+=1

#所有点都访问过表示存在mst
if num==n:
print l
else:
print -1

• 作业2

08-图8 How Long Does It Take（25 分）
Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of activity check points (hence it is assumed that the check points are numbered from 0 to N−1), and M, the number of activities. Then M lines follow, each gives the description of an activity. For the i-th activity, three non-negative numbers are given: S[i], E[i], and L[i], where S[i] is the index of the starting check point, E[i] of the ending check point, and L[i] the lasting time of the activity. The numbers in a line are separated by a space.

Output Specification:
For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output “Impossible”.

Sample Input 1:
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

Sample Output 1:
18

Sample Input 2:
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

Sample Output 2:
Impossible

# -*- coding: utf-8 -*-
"""
Created on Wed May 02 11:09:15 2018

"""

n,m=map(int,raw_input().split(' '))

#记录点和边
l={}

#记录入度
r=[0 for i in range(n)]

#记录每个点指向的点
x={}
for i in range(n):
x[i]=()

for i in range(m):
a,b,c=map(int,raw_input().split(' '))
l[(a,b)]=c
r[b]+=1
x[a]+=(b,)

#记录时间
s=0
#记录访问个数
cnt=0
#记录入度为0的点
queue=[]
#至第n个点的花费时间
f=[0 for i in range(n)]

#将入度为0的点记录着队列中
for i in range(n):
if r[i]==0:
queue.append(i)

while(len(queue)>0):
v=queue.pop(0)
cnt+=1
for i in x[v]:
r[i]-=1
if r[i]==0:
queue.append(i)
temp=f[v]+l[(v,i)]
if f[i]<temp:
f[i]=temp
if cnt==n:
print max(f)
else:
print "Impossible"
• 作业3

08-图9 关键活动（30 分）

7 8
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2

17
1->2
2->4
4->6
6->7

# -*- coding: utf-8 -*-
"""
Created on Wed May 02 12:50:58 2018

"""
n,m=map(int,raw_input().split(' '))

#记录点和边
l={}

#记录入度
r=[0 for i in range(n)]
#记录出度
c=[0 for i in range(n)]

#记录每个点指向的点
x={}
#记录指向每个点的点
y={}
for i in range(n):
x[i]=()
y[i]=()

for i in range(m):
a,b,d=map(int,raw_input().split(' '))
a=a-1
b=b-1
l[(a,b)]=d
#入度
r[b]+=1
#出度
c[a]+=1
x[a]+=(b,)
y[b]+=(a,)

#记录时间
s=0
#记录访问个数
cnt=0
#记录入度为0的点
queue=[]
#至第n个点的花费时间
f=[0 for i in range(n)]

#将入度为0的点记录着队列中
for i in range(n):
if r[i]==0:
queue.append(i)

#记录earliest
while(len(queue)>0):
v=queue.pop(0)
cnt+=1
for i in x[v]:
r[i]-=1
if r[i]==0:
queue.append(i)
temp=f[v]+l[(v,i)]
if f[i]<temp:
f[i]=temp

length=max(f)

#计算latest
g=[length for i in range(n)]

#存放出度为0的点
queue=[]
for i in range(n):
if c[i]==0:
queue.append(i)

while(len(queue)>0):
v=queue.pop(0)
for i in y[v]:
c[i]-=1
if c[i]==0:
queue.append(i)
temp=g[v]-l[(i,v)]
if g[i]>temp:
g[i]=temp

if cnt==n:
print length
for i in range(n-1):
for j in range(n,-1,-1):
if (i,j) in l:
if (g[j]-f[i]-l[(i,j)])==0:
print str(i+1)+'->'+str(j+1)
else:
print 0