【拓扑排序+带权值的拓扑排序】【学习一天才明白！一天思考总结！】基础实验6-2.6 最短工期

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
文章字体风格：
红色文字表示：重难点
蓝色文字表示：思路以及想法
　
如果大家觉得有帮助的话，感谢大家帮忙点赞！收藏！转发！

1. 什么是拓扑排序

拓扑排序经常用于类似于闯关游戏排序之中。

如：
难度系数为一的系列中，有关卡1，2，3
难度系数为二的关卡中，有关卡4，5，
难度系数为三的关卡中，有关卡6

我们规定 从关卡1,2可以走到 关卡4；从3 可以走到 5

但是
1. 如果是一个人去完成这些关卡，那么就必须完成一个系列，才能进入下一个系列，那他进行的关卡，就必须是 1,2，3,4，5,6的顺序了（具体如下）

2. 但是如果是一个队伍去完成关卡，那么就可以从一个系列的关卡中一起去完成（这个想法会用到带权值的拓扑排序）

一个人的闯关顺序（正常的拓扑排序）

首先，我们先总结一下，如果一个人，是怎么去闯关的？
如果一个人，那就需要按着难度系数的系列关卡去闯卡，在图中，如何判断每个节点是一个系列的呢？
我们可以通过节点的入读来判断系列，我们看，1 2 3关卡节点的入读都是0，而其他的都是>0.我们就从这一点信息，去判断闯关顺序就好了。
例如，从1开始闯关，走到1后，把1指向节点的入读–。如果节点入度为0，就说明可以进入闯关准备阶段，那就让该节点入队列就好了（我们用一个队列，存储可以进入闯关阶段的节点。因为如果1指向的是4,4只有一个入读，那么说明走完1, 那就可以走4， 但是并非如此，因为还有2 ， 3节点没有走，所以，说明，我们再最开始先需要把 1 2 3节点就入队列）
如上，去遍历节点，便可得到一个人闯关的顺序！！！

一“队”人的闯关顺序（带权值的拓扑排序）

如果是一队人的话，那么就可以从难度系数为1的三个节点，分三波人同时开始闯关，那么这一队人同时可以完成关卡1 2 3 ，然后再同时完成 4 5 然后再同时完成 6

再上一个层次，如果把闯每个关卡加上一个时间限制呢，也就是比如，闯第一关卡，一定会用时 6个小时，第二个用时3个小时，具体如图

问，最少需要多少时间可以完成整个地图关卡？
当然，最少时间，一定是在所有关卡全部都完成的最少时间。

那么我们开始想：
一队人，同时进行1 2 3关卡，
会出现的路线有：
1 4 6
2 4 6
3 5 6
我们用二维数组存储每个节点之间的闯关时间，
一个一维数组存储每个节点的入度
一个一维数组记录走到该节点的最大时间（只有最大时间才能保证这个点之前的所有节点都完成）
一个变量sum即可记录最短时间
接下来，就是，我们从一个人闯关的路线，去遍历图，如果完成该关卡的时间+走到该关卡之前的时间 大于 sum值。那么就更新sum值，因为当出现完成该关卡的时间+走到该关卡之前的时间 大于 sum值，那么最终完成 时间一定是 以完成任务的为标准的最短时间，如果以sum值不变，那么就说明没有完成全部任务。
那么，同理，如果出现完成该关卡的时间+走到该关卡之前的时间 小于 sum。那么就不用更新sum值，因为sum值已经是表示完成任务的最小值，如果再更新就说明其他任务没有时间完成了，并且出现此情况，就说明其它队伍正在进行闯关，也就是其实是一起闯关的（就好比烧水和墩地，虽然是两件事，但可以用同一个时间去进行，因为人多嘛）
按着这个思路，完成的sum值便是完成所有任务后的最短时间

拓扑排序的条件

如果有环图不能进行拓扑排序（因为没有意义，比如打完关卡难度为三的图，再去打难度一的图，这样是没有意义的）
那么怎么判断一个图是不是有环图呢？
我们定义一个变量记录
我们每次入队列的时候，该变量++即可
最后我们判断该变量是否等于所有节点数，如果等于便不是有环图，如果不等于，那么就是有环图

例题 基础实验6-2.6 最短工期

#include
#include
using namespace std;
int main()
{
    queue<int>l;
    int a,b,c[101][101],d[101]={0},e[101]={0},f,g,h,i,j,ma,ans=0;
// c数组用来存储节点，
/*d数组用来记录完成每个节点的最大时间（只有时间最大，
才能保证该节点的所有节点都完成）并且是最大时间，
不是时间之和*/
//e数组用来记录每个节点的入读数
    for(f=0;f<101;f++)
        for(g=0;g<101;g++)
            c[f][g]=-1;
    cin>>a>>b;
    while(b--)
    {
        cin>>f>>g>>h;
        c[f][g]=h;
        e[g]++;
    }
// 1. 把系列一入队列
    for(f=0;f<a;f++)
        if(e[f]==0)
        {
            ans++;
            l.push(f);
            e[f]=-1;
        }
// 2. 取出队头，遍历连接点，比较两个最大值（走到该节点的最大值，最短时间的最大值）
// 3. 遍历一个节点，入读--如果为0了，入队列
    while(!l.empty())
    {
        f=l.front();
        l.pop();
        for(g=0;g<a;g++)
        {
            if(c[f][g]!=-1&&e[g]>0)
            {
                e[g]--;
                d[g]=max(d[g],d[f]+c[f][g]);
                ma=max(ma,d[g]);
                if(e[g]==0)
                {
                    l.push(g);
                    e[g]=-1;
                    ans++;
                }
            }
        }
    }
//*****最后需要注意的一点,判断是否为有环图
    if(ans!=a)
        cout<<"Impossible"<<endl;
    else
        cout<<ma<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

模板

// 1. 把系列一入队列
// 2. 取出队头，遍历连接点，比较两个最大值（走到该节点的最大值，最短时间的最大值）
// 3. 遍历一个节点，入读–如果为0了，入队列
//*****最后需要注意的一点,判断是否为有环图

拓扑排序

void topological_sort(){ 
	queue<int>q;
    vector<int>edge[n];
    for(int i=0;i<n;i++)  //n：结点的总数
        if(in[i]==0) q.push(i);  //将入度为0的点入队列
    vector<int>ans;   //ans 为拓扑序列
    while(!q.empty())
    {
        int p=q.front(); q.pop(); // 选一个入度为0的点，出队列
        ans.push_back(p);
        for(int i=0;i<edge[p].size();i++)
        {
            int y=edge[p][i];
            in[y]--;
            if(in[y]==0) q.push(y);  
        }
    }
    if(ans.size()==n){
        for(int i=0;i<ans.size();i++)
            cout<<ans[i]<<" "; 
    }else cout<<"No Answer!\n";   //  ans中的长度与n不相等，存在环 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

带权值的拓扑排序

#include
using namespace std;
int dis[105][105],ru[105],f[105];
int n,ans,cnt=0;

void topological_sort(){
	while(1){
		int flag=0;
		for(int i=0;i<n;i++){
    		if(!ru[i]){  //入度为0的顶点（即没有前驱任务的任务，那么这个任务就可以做了） 
    			ru[i]--;//变为-1，也就是这个任务做完了，后面不用考虑了 
    			cnt++;
    			flag=1;
    			for(int j=0; j<n; j++){
    				if(dis[i][j]!=-1){//存在以i为前驱任务的任务 
                    	ru[j]--; // 入度减一（把i任务去掉了，则j的前驱任务少了一个） 
                    	f[j]=max(f[j],f[i]+dis[i][j]); //选择最长的工作时间 
                   		ans=max(ans,f[j]);//统计最早完工时间 
                	}	
				}
			}
		}
		if(!flag) break;  //不存在入度为0的点，跳出循环 	
	}
	if(cnt==n) cout<<ans<<endl; //全部顶点和边成功去掉 
	else cout<<"Impossible"<<endl;//存在环 
}

int main(){
	int m, p, x, y;
	cin>>n>>m;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			dis[i][j]=-1;//初始边的权都为-1，因为工作时长可能是0，所以初始dis都赋值为-1 
	while(m--){
		cin>>x>>y>>p;
		dis[x][y]=p;
		ru[y]++;//ru[y]顶点y的入度,(即题目中的y任务的前驱任务们) 
	} 
	topological_sort();    //拓扑排序
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43