Part1:回顾

1.最小生成树

首先看下最小生成树的定义。最小生成树这个名字中有三重信息，首先树，其次是生成树，最后是最小生成树，具体如下。

生成最小生成树使用的是贪心算法，一般有两种，分别为Prim算法以及Kruskal算法，下面分别介绍。

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

2.拓扑排序

首先看一个计算机专业课排课的问题，计算机有许多门课，有的课学习之前需要先学习其他的课程，这样就有一个排序问题，课程少还好，如果有几十门课，那么人工排课就太麻烦了，所以需要将这个问题抽象出来，这就有了拓扑排序的概念。

先从实际过程中看下排序的过程，回到之前的排课的例子，最先修的课程一定是没有预修课程的，换成图的语言就是先抛出入度为0的点，抛出入度为0的点之后，要将其指向的点的入度减1，随后重复此操作直至全部抛出即可。

下面把这个过程转化为算法,思路就是每次抛出入度为0的点。

这样直接操作的话时间复杂度较高，主要是由于每次都要找入度为0的点，所以索性将入度为0的点存在一个容器中，这样可以减少算法复杂度，这样就有了第二种算法。

3. 关键路径问题

最后介绍一下拓扑排序的应用，关键路径问题。首先看下背景，工程中可以分为很多的个子工程，有些子工程需要安排在特定的子工程后面，这样就可以利用到之前的拓扑排序。有些子工程可能需要多个工程在其之前完成，每个子工程需要的时间不同，这样就会有时间多余的情况，形成机动时间，关键路径问题就是找到这样的点。下面看下具体定义以及例子。

Part2:作业

作业1

08-图7 公路村村通（30 分）
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

输入样例:
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

这题就是个最小生成树的问题，从M的规模可以看出，这题使用Kruskal算法效率较高。

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

@author: Administrator
"""
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

这题是关键路径问题的简化版，每次将入度为0的点k抛出，计算Earliest[k]即可。

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

@author: Administrator
"""

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 分）
假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。
比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。
但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。
任务调度问题中，如果还给出了完成每个子任务需要的时间，则我们可以算出完成整个工程需要的最短时间。在这些子任务中，有些任务即使推迟几天完成，也不会影响全局的工期；但是有些任务必须准时完成，否则整个项目的工期就要因此延误，这种任务就叫“关键活动”。
请编写程序判定一个给定的工程项目的任务调度是否可行；如果该调度方案可行，则计算完成整个工程项目需要的最短时间，并输出所有的关键活动。

输入格式:
输入第1行给出两个正整数N(≤100)和M，其中N是任务交接点（即衔接相互依赖的两个子任务的节点，例如：若任务2要在任务1完成后才开始，则两任务之间必有一个交接点）的数量。交接点按1~N编号，M是子任务的数量，依次编号为1~M。随后M行，每行给出了3个正整数，分别是该任务开始和完成涉及的交接点编号以及该任务所需的时间，整数间用空格分隔。

输出格式:
如果任务调度不可行，则输出0；否则第1行输出完成整个工程项目需要的时间，第2行开始输出所有关键活动，每个关键活动占一行，按格式“V->W”输出，其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是：任务开始的交接点编号小者优先，起点编号相同时，与输入时任务的顺序相反。

输入样例:
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

这题是完整的关键路径问题，首先每次抛出入度为0的点，正向计算Earliest[k]。计算完Earliest之后，每次抛出出度为0的点，反向计算Latest[k]。最后抛出Earliest[k]=Latest[k]的点即可。

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

@author: Administrator
"""
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