c++关键活动

关键活动：

一个工程项目一般是由一些子任务构成，子任务之间有的可以并行执行，有的必须在完成某些任务之后才可以执行，给出每个任务完成所需要的时间，则可以算出整个工程所需要的最短时间，在这些子任务中，有些任务推迟几天也不会影响这个工程的工期，但是有些任务必须准时完成，否则会延误整个工期，这种活动称为关键活动。

1. 该问题的本质是一个图，图可以用邻接表来存储，邻接表是多个链表组成的，邻接表的本质是链表数组，要想实现邻接表的删除，插入等操作，首先需要实现链表的删除插入等操作，在邻接表的处理过程中只需要对该数组中的确定位置处进行插入，删除等操作;

1. 对于每条边的始发点都需要用链表来存储，其中头节点表示始发点，next指针指向所有与该条边连接的点的信息；
2. 链表由多个节点构成，每个节点包含顶点和权值；
3. 在每条链表的初始化中，需要将每个节点的next指针指向NULL；

2.计算每个节点的最早开始时间是计算从源点开始到该点的所有路径中的最大值，源点是不需要任何子任务的基础上就可以开始的节点，所以需要知道每个节点的入度和出度；

3.计算每个节点的最晚开始时间是从终点开始，倒退，每个节点的最晚开始时间是其所指向的点的最晚开始时间减去这条边的权值，当有多条路径时，选择计算的最晚开始时间的最小值即可；

4.计算每个活动点的最早开始时间：

     1>将源点的最早开始时间设定为0，运用到队列的结构，将源点压入到队列中；

      2>从队列中弹出元素，然后将从该点出发的边都删除掉，继续判断哪些点的入度为0，将这些点继续压入到队列中，在压入到队列的时候顺便判断从源点到该点走这条路径的长度是否比已有的长度大，如果大，则进行更新，直到队列为空为止；

     3>在整个过程中对于已经压入到过队列的元素需要进行标记，防止陷入无限循环；

      4>如果压入到队列的元素的个数小于总的节点的个数，则证明存在着环路，存在环路证明该任务不能调度；

5.计算每个活动点的最晚开始时间：

（1）将终点的最晚开始时间设定为该点的最早开始时间；

   (2)找到到该点的活动点，该活动点的最晚开始时间为该边的到达的点的最晚开始时间减去该条边的长度，并且当有多条路径的时候，该活动点的最晚开始时间为多条路径的最小值；

   (3)终点的确定根据他的出度，如果一个活动点的出度为0，则该点就是终点；

   (4)将终点压入到队列中，从队列中弹出首元素，将到该点的边的起始点压入到队列中，并且在压入队列的过程中不断更新最晚开始时间，直到队列为空；

6.伪代码

拓扑排序：

Void toposort()

{

  将入度为0的节点压入到队列中；

While(队列不为空）

{

Node q=弹出队首元素；

删除队首元素；

将q点出去的边的终点的最早开始时间进行更新，每次存储较大值；

将aist[q]该条链表删除，也就是删除从该点出发的边，减小相对应的点的入度；

将入度为0的节点压入到队列中；

}

}

反拓扑排序：
Void latesort()

{

 将出度为0的节点压入到队列中；

While(队列不为空）

{

Node q=弹出队首元素；

删除队首元素；

将到达q点的边的起点的最晚开始时间进行更新，每次存储较小值，同时将该点压入到队列中；

}

}

不足：

这个题目我忽略了一点，也就是对于工程来讲，终点不应该唯一

对于这种情况的处理，最晚开始时间需要选择所有终点中的最大值，在反向拓扑排序的过程中也需要先将最早开始时间的最大值的终点压入到队列中再进行处理。

附上代码：

#include<iostream>
#include<queue>
#include<malloc.h>
#define MAX 1000
using namespace std;
int begin[100];
int end[100];
int label[100][100]={0};//用来<i，j>是否存在关键路径，值为0不存在，为1存在
int mark[100]={0};//存储从开始项目到结束项目的单条关键路径
int mm=2;//用来标记该路径上的点的个数 
int huidian;
struct chainnode
{
	int element;//表示顶点
	int values;//表示权值 
	chainnode *next;
	chainnode(int e,int v,chainnode *n)
	{
		element=e;
		values=v;
		next=n;
	}
};
struct chain
{
	int listsize;
	chainnode *firstnode;
	chain()
	{
		listsize=0;
		firstnode=NULL;
	 } 
	int size()
	{ 
	    return listsize;
	} 
	int indexof(int x)
	{
		chainnode *currentnode=firstnode;
		int index=0;
		while(currentnode!=NULL &&currentnode->element != x)
		{
			currentnode=currentnode->next;
			index++;
		}
		if(currentnode==NULL)
		return -1;
		else
		return index;
	}
	void insert(int index,int thelement,int values)
	{
		if(index<0||index>listsize)
		return;
		if(index==0)
		firstnode=new chainnode(thelement,values,firstnode);
		else
		{
			chainnode *p=firstnode;
			for(int i=0;i<index-1;i++)
			p=p->next;
			p->next =new chainnode(thelement,values,p->next);
		}
		listsize++;
	}
	void erase(int index)
	{
		chainnode *deletenode;
		if(index==0)
		{
			deletenode=firstnode;
			firstnode=firstnode->next;
		}
		else
		{
			chainnode *p=firstnode;
			for(int i=0;i<index-1;i++)
			p=p->next;
			deletenode=p->next;
			p->next=p->next->next; 
		}
		listsize--;
		delete deletenode;
	}
	int* eraseelement(int v) 
    {
    	chainnode *current=firstnode;
    	chainnode *p=NULL;
    	while(current!=NULL&&current->element!=v)
    	{
    		p=current;
    		current=current->next;
    	}
    	if(current==NULL)
    	return NULL;
    	int *theelement=&current->element;
    	if(p!=NULL)
    	p->next=current->next;
     	else
    	firstnode=current->next;
    	delete current;
    	listsize--;
    	return theelement;
    }
};
struct edge
{
	int v1;
	int v2;
	int value;
	int getv1()
	{
		return v1;
	}
	int getv2()
	{
		return v2;
	}
	int getvalue()
	{
		return value;
	}
};
class linkeddigraph
{
	protected:
		int n;//表示顶点个数
		int m;//表示边数
		chain *alist;
	public:
	    linkeddigraph(int num);
		~linkeddigraph()
		{
			delete []alist;
		}
		void insert(edge e);
		int indegree(int v);
		int outdegree(int v); 
		void eraseedge(int i,int j);
		void toposort();
		void latetopsort();
		void dfs(int x,int y,int *temp);
		void print();
};
linkeddigraph::linkeddigraph(int num)
{
	n=num;
	m=0;
	alist=new chain[n+1];
	for(int i=0;i<=n;i++)
	alist[i].firstnode =NULL;
	
}
void linkeddigraph::insert(edge e)
{
	int v1=e.getv1();
	int v2=e.getv2();
	int v=e.getvalue();
	if(alist[v1].indexof(v2)==-1)//新边
	{
		alist[v1].insert(0,v2,v);
		m++; 
	} 
}
int linkeddigraph::indegree(int v)
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(alist[i].firstnode!=NULL)
		if(alist[i].indexof(v)!=-1)
		sum++;
	}
	return sum;
}
int linkeddigraph::outdegree(int v)
{
	if(alist[v].firstnode !=NULL)
	return alist[v].size();
	else
	return 0;
}
void linkeddigraph::eraseedge(int i,int j)
{
	int *v=alist[i].eraseelement(j);
	if(v!=NULL)
	m--;
}
void linkeddigraph::toposort() 
{
	queue<int> q;
	int vis[n+1]={0};
	int cnt=0;
	for(int i=0;i<=n;i++)
	{
		begin[i]=0;
		end[i]=0;
	}
	int i;
	for(i=1;i<=n;i++)
	{
		if(indegree(i)==0)
		{
			q.push(i);
			vis[i]=1;
			break;
		}	
	}
	while(!q.empty())
	{
		int temp=q.front();
		q.pop();
		int temped[100];
		int count=0;
		cnt++;
		chainnode *p=alist[temp].firstnode;
		while(p!=NULL)
		{
	    	temped[count++]=p->element;
			if(begin[p->element]<p->values+begin[temp])
			begin[p->element]=p->values+begin[temp];
			p=p->next;
		}
		for(int i=0;i<count;i++)
		eraseedge(temp,temped[i]);
		for(int i=1;i<=n;i++)
     	{
     		if(indegree(i)==0&&vis[i]==0)
    		{
    			q.push(i);
	    		vis[i]=1;
    		}	
    	}
	}
	if(cnt<n)
	{
		cout<<"该图有环路"<<endl;
	}
}
void linkeddigraph::latetopsort() 
{
	queue<int> q;
	int max=begin[n]; 
	for(int i=0;i<=n;i++)
	end[i]=MAX;
	for(int i=1;i<=n;i++)
	{
		if(outdegree(i)==0)
		{
			q.push(i);
			break;
		}
	}
	end[q.front()]=begin[q.front()];
	while(!q.empty())
	{
		int temp=q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			if(alist[i].indexof(temp)!=-1)
			{
				q.push(i); 
				int location=alist[i].indexof(temp); 
				chainnode *p=alist[i].firstnode;
				for(int j=0;j<location;j++)
				p=p->next;
				int v=p->values;
				if(end[i]>end[temp]-v)
				end[i]=end[temp]-v;
			}
		}
	}
	cout<<"关键活动有:";
	for(int i=1;i<=n;i++)
	{
		if(begin[i]==end[i])
		cout<<i<<" ";
	}
	cout<<endl;
}
void linkeddigraph::dfs(int x,int y,int *temp)//temp中存储的是关键活动 ,x是起点，y是汇点 
{
	if(x==y)//到达结束点 
	{
		int v;
		cout<<mark[1];
		for(int i=2;i<mm;i++) 
		{
			v=mark[i];
			cout<<"->"<<v;
		}
		cout<<endl;
	}
	else
	{
		for(chainnode *p=alist[x].firstnode;p!=NULL;p=p->next)
		{
			for(int i=0;i<n;i++)
			{
				if(p->element==temp[i]&&p->element!=x)
				{
					label[x][p->element]=1;  
					break;
				}
			 } 
			 if(label[x][p->element]==1)//证明存在着关键路径
			 {
			 	label[x][p->element]=0;//不可重复选择关键路径上的点
				mark[mm++]=p->element; 
			 	dfs(p->element,y,temp);
			 	label[x][p->element]=1;//还原
			 	mm--;//返回上层递归在具有多条关键活动的项目后重新选择新的一条关键路径项目点  
		//	 	cout<<p->element <<"->";
			  } 
		}
	}
} 
void linkeddigraph::print() 
{
	int temp[10];
	int count1=0;
	int count2=0;
	int temped[n];
//	int huidian;
	for(int i=1;i<=n;i++)
	{
		if(end[i]==begin[i])
		{
			if(outdegree(i)==0)
			huidian=i;
			else if(indegree(i)==0)
			temp[count1++]=i;
			else
			temped[count2++]=i;
		}
	}
	//cout<<huidian<<endl;
//	cout<<temp[0]<<"->";
	for(int i=0;i<count1;i++)
	{
		mark[1]=temp[i];
		dfs(temp[i],huidian,temped);
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	linkeddigraph g(n);
	vector<edge> vec;
	int temp[n+1];
	int count=0;
	for(int i=0;i<m;i++)
	{
		edge e;
		cin>>e.v1>>e.v2>>e.value;
		g.insert(e); 
		vec.push_back(e); 
	}
	g.toposort();
	for(int i=0;i<vec.size();i++)
	g.insert(vec[i]); 
	g.latetopsort();
	cout<<"最早开始时间:";
	for(int i=1;i<=n;i++)
	cout<<begin[i]<<" ";
	cout<<endl;
	cout<<"最晚开始时间:";
	for(int i=1;i<=n;i++)
	cout<<end[i]<<" ";
	cout<<endl;
	g.print();
//	cout<<huidian<<endl;
	return 0;
}