A27920. 最短工期一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。输入首先第一行给出两个正整数：项目里程碑的数量 N（≤ 100）和任务总数 M。这里的里程碑从 0 到 N-1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务…
填空题
困难
知识点
题目描述
最短工期
一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。
输入
首先第一行给出两个正整数：项目里程碑的数量 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样例#2：
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5样例输出
样例#1：
18样例#2：
Impossible参考答案
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INFO_MAX_SIZE 20
#define MAX_SIZE 200
//领接矩阵存储的图
struct Graph{
int vexNumber;
string vexInfo[INFO_MAX_SIZE];
int adjMatrix[MAX_SIZE][MAX_SIZE];
};
//弧结点定义
struct ArcNode{
int weight;//弧上的信息部分
int adj;//邻接点的序号
ArcNode *nextarc;
};
//顶点结点定义
struct VexNode{
string Info;
ArcNode *firstarc;
};
//领接表结构的图的定义
struct linkGraph{
VexNode *vexes;
int vexnumber;
};
struct tempNode{
int col;
int row;
int weight;
//tempNode *next;
};
struct temp{
int num;
tempNode *docu;
};
int preInitGraph(linkGraph &G,const Graph &g){
G.vexes=new VexNode[g.vexNumber];
G.vexnumber=g.vexNumber;
for(int i=0;i<g.vexNumber;i++){
G.vexes[i].firstarc=NULL;
}
return 0;
}
//将邻接矩阵存储的图转换为领接表存储的图
void InitGraph(linkGraph &G,const Graph &g,temp &t){
preInitGraph(G,g);
for(int i=0;i<t.num;i++){
int a,b,c;
a=t.docu[i].row;b=t.docu[i].col;c=t.docu[i].weight;
ArcNode *p=new ArcNode();
p->nextarc=NULL;
p->weight=c;
p->adj=b;
ArcNode *q=G.vexes[a].firstarc;
if(G.vexes[a].firstarc==NULL)
G.vexes[a].firstarc=p;
else{
while(q->nextarc!=NULL){
q=q->nextarc;
}
q->nextarc=p;
}
}
}
int TopologicalSort(linkGraph LG,int Topo[]){
vector<int>indegree(LG.vexnumber);
for(int i=0;i<LG.vexnumber;i++) indegree[i]=0;
for(int i=0;i<LG.vexnumber;i++){
for(ArcNode *p=LG.vexes[i].firstarc;p!=nullptr;p=p->nextarc)
indegree[p->adj]++;
}
//入度为零的点入栈
stack<int>s;
for(int i=0;i<LG.vexnumber;i++){
if(indegree[i]==0) s.push(i);
}
int i=0;
while(!s.empty()){
int j=s.top();s.pop();
Topo[i++]=j;
//将Vj邻接点入度减一，减为0的入栈
for(ArcNode *p=LG.vexes[j].firstarc;p!=nullptr;p=p->nextarc){
indegree[p->adj]--;
if(indegree[p->adj]==0) s.push(p->adj);
}
}
if(i==LG.vexnumber) return 0;
else return 1;
}
//输出领接表存储的图
void PrintGraph(const linkGraph &G){
for(int i=0;i<G.vexnumber;i++){
cout<<G.vexes[i].Info;
ArcNode *p=G.vexes[i].firstarc;
cout<<i;
while(p!=NULL){
cout<<" --> "<<p->adj;
p=p->nextarc;
}
cout<<endl;
}
}
//vector<pair<int,int>>
void CriticalPath(linkGraph G){
int Topo[G.vexnumber];
if(TopologicalSort(G,Topo)){
cout<<"Impossible"<<endl;
return ;
}
vector<pair<int,int>>aArcs;
//统计入度
vector<int>indegree(G.vexnumber);
for(int i=0;i<G.vexnumber;i++) indegree[i]=0;
for(int i=0;i<G.vexnumber;i++){
for(ArcNode *p=G.vexes[i].firstarc;p!=nullptr;p=p->nextarc)
indegree[p->adj]++;
}
//入度为0进栈
stack<int>s;
for(int i=0;i<G.vexnumber;i++){
if(indegree[i]==0) s.push(i);
}
//拓扑排序，计算ve
vector<int>ve(G.vexnumber);
for(int i=0;i<G.vexnumber;i++) ve[i]=0;
stack<int>s2;//记录拓扑序
while(!s.empty()){
int i=s.top();s.pop();
s2.push(i);
//遍历Vi邻接点
for(ArcNode *p=G.vexes[i].firstarc;p!=nullptr;p=p->nextarc){
//邻接点入度减一，为0入栈
int j=p->adj;
indegree[j]--;
if(indegree[j]==0) s.push(j);
//修正Vj的Ve值
if(ve[i]+p->weight>ve[j]){
ve[j]=ve[i]+p->weight;
}
}
}
int max=0;
for(int i=0;i<G.vexnumber;i++){
if(ve[i]>max) max=ve[i];
}
cout<<max<<endl;//针对本题，函数写到这行就够了。加上下面的是计算关键路径的完整代码。
//按逆拓扑序计算vl，终点的ve值作为vl的初值
vector<int>vl(G.vexnumber);
int maxve=ve[s2.top()];
for(int i=0;i<G.vexnumber;i++) vl[i]=maxve;
while(!s2.empty()){
int i=s2.top();s2.pop();
//用Vi的邻接点来修正Vi的Vl值
for(ArcNode *p=G.vexes[i].firstarc;p!=nullptr;p=p->nextarc){
int j=p->adj;
if(vl[j]-p->weight<vl[i])
vl[i]=vl[j]-p->weight;
}
}
int sum=0;
//遍历所有弧，计算弧的e和l值，挑选关键弧（e和l相等的弧）
for(int i=0;i<G.vexnumber;i++){
for(ArcNode *p=G.vexes[i].firstarc;p!=nullptr;p=p->nextarc){
int e=ve[i];
int l=vl[p->adj]-p->weight;
if(e==l){
//记录一条关键弧
aArcs.push_back(make_pair(i,p->adj));
sum+=p->weight;
}
}
}
}
int main(){
//freopen("/config/workspace/test/test","r",stdin);
int n,m;
cin>>n>>m;
Graph G;
G.vexNumber=n;
temp t;
t.num=m;
t.docu=new tempNode[m];
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
t.docu[i].row=a;
t.docu[i].col=b;
t.docu[i].weight=c;
}
linkGraph LG;
InitGraph(LG,G,t);
//test
//PrintGraph(LG);
CriticalPath(LG);
return 0;
}
上一题
下一题