12 、关键活动

假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和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

#include 
using namespace std;
int maxn = 110;
int INF = 0x3f3f3f3f;//定义一个很大的数INF且后面代码不可更改INF的值
int G[maxn][maxn];//G,e1,d,d1
int deg1[maxn], deg[maxn];//出度，入度
int el[maxn][maxn], d[maxn], d1[maxn];
int V, E, MAX_len = 0;
//判断是否可调度，计算最早发生时间
int toposort()
{memset(d, 0, sizeof d);//d数组记录各点最短发生时间int que[maxn], l = 0, r = 0;for (int i = 1;i <= V;i++)if (deg[i] == 0)//查找各点入读，若为0，则进栈que[r++] = i;while (l != r)//队中有元素{int v = que[l++];//v赋值为队首元素，队首元素出队，然后接下来后面的结点入度减一for (int i = 1;i <= V;i++)if (G[v][i] != INF)  //如果后面有邻接点{if (--deg[i] == 0) que[r++] = i;//入度减一后入度为0则入队if (d[i] < d[v] + G[v][i])//求入度为0的点到该点的最长路径d[i] = d[v] + G[v][i];}}for (int i = 1;i <= V;i++) MAX_len = max(MAX_len, d[i]);//记录最长路径权值，找起点到各点的最长路径if (r != V) return -1;//当出队的个数等于图节点个数的时候是无环图，不等于则是有环的else return 1;
}
//求 关键路径
void opposite_toposort()
{memset(d1, INF, sizeof(d1));int que[maxn], l = 0, r = 0;for (int i = 1;i <= V;i++)if (deg1[i] == 0) { que[r++] = i;d1[i] = MAX_len;//令出度为0的点距离最大}  //出度为0则入队while (l != r)  //队列不空{int v = que[l++];//赋值队首元素，将队首元素出对for (int i = 1;i <= V;i++)if (G[i][v] != INF)//当此点前面的点的出度-1后为零则此结点入队{if (--deg1[i] == 0)//若去掉v后某元素的出度为0，则入队que[r++] = i;if (d1[i] >= d1[v] - G[i][v])//必须是>=否则无法得出多条关键路径 {d1[i] = d1[v] - G[i][v];el[i][v] = d1[v] - d[i] - G[i][v];//e1[][]=最长的路径权值-活动持续时间-该活动的最早开始时间}//在后面判断e1的值为0即为关键活动}}
}
int main()
{memset(G, INF, sizeof G);           //数组填充INFmemset(el, INF, sizeof el);cin>>V>>E;for (int i = 0; i < E; i++){int a, b, c;cin>>a>>b>>c;G[a][b] = c;          //G数组用来存各边的权值deg[b]++,deg1[a]++;    //a的出度加1，b的入读加1}if (!toposort())         //如果不可调度(有环)，结束程序{printf("0\n");return 0;}opposite_toposort();       //求关键路径printf("%d\n", MAX_len);for (int i = 1;i <= V;i++)for (int j = V;j >= 1;j--)if (el[i][j] == 0)printf("%d->%d\n", i, j);
}

13 、任务调度的合理性

假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。

但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。

输入格式:

输入说明：输入第一行给出子任务数N（≤100），子任务按1~N编号。随后N行，每行给出一个子任务的依赖集合：首先给出依赖集合中的子任务数K，随后给出K个子任务编号，整数之间都用空格分隔。

输出格式:

如果方案可行，则输出1，否则输出0。

输入样例1:

12
0
0
2 1 2
0
1 4
1 5
2 3 6
1 3
2 7 8
1 7
1 10
1 7

输出样例1:

1

#include
using namespace std;
vectorG[1000];
int n,in[1000],num=0;
queueq;
int TopSort(){for(int i=1;i<=n;i++)if(in[i]==0)q.push(i);while(!q.empty()){int v=q.front();q.pop();for(int i=0;i>n;for(i=1;i<=n;i++){cin>>k;in[i]=k;for(j=0;j>t;G[t].push_back(i);}}if(TopSort()==n)cout<<1;else cout<<0;
}

14、 最短工期

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式：

首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。

输出格式：

如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

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

输出样例 1：

18

#include
#define N 110
using namespace std;
struct G{int y,d;
};
vectorg[1001];
int n,m,d[N]={0},in[N]={0},maxlen=0,num=0;
int sort()
{queueq;for(int i=0;i>n>>m;for(int i=0;i>a>>b>>c;G temp={b,c};g[a].push_back(temp);in[b]++;}if(sort()!=n){cout<<"Impossible";return 0;}cout<

7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 3

The length of the shortest path between 0 and 3 is 2.

#include
#define inf 10000001
using namespace std;
int n,m,g[111][111],visited[111],d[111],a,b;
void sort(int a,int l)
{int i,count=0,temp[111];for(i=0;i>n>>m;int i,j,k;for(i=0;i>a>>b;g[a][b]=1;g[b][a]=1;}cin>>a>>b;visited[a]=1;d[a]=0;sort(a,1);if(visited[b]==0){printf("There is no path between %d and %d.",a,b);}else{printf("The length of the shortest path between %d and %d is %d.",a,b,d[b]);}
}

4
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0

0 3 2 1 
6 0 4 7 
2 5 0 3 
3 6 1 0 

#include
using namespace std;
int g[52][52],n;
void FloydWarshall()
{for(int k=0;kg[i][k]+g[k][j])g[i][j]=g[i][k]+g[k][j];
}
int main()
{cin>>n;int i,j,k;memset(g,10001,sizeof g);int a=g[0][0];for(i=0;i>k;if(k!=0)g[i][j]=k;}getchar();}FloydWarshall();for(i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！