aoe.cpp

设计一个项目

#include<iostream.h>
typedef int dataType;
#include"stack.h"
struct arc
{int first;
int last;
int info;
};
void main()
{int n;//n为图中的结点数
	cout<<"输入图的结点数："<<endl;
cin>>n;
int *a=new int[n];//a[i]数组用来存储以第i个结点为弧尾的弧数
int *indegree=new int[n];//每个顶点的入度数
for(int t=0;t<n;t++)
indegree[t]=0;
int temp=0,ta,m;
for(int i=0;i<n;i++)
{cout<<"请输入以第"<<i<<"个顶点为弧尾的弧数："<<endl;
cin>>a[i];
if(temp<a[i]) temp=a[i];
}//找出最大的出度
arc *b=new arc[n*temp];
for(int p=0;p<n;p++)
{for(int j=0;j<a[p];j++)
{b[p*temp+j].first=j;
cout<<"输入以第"<<p<<"个顶点为出度的第"<<j<<"条弧的终点"<<endl;
cin>>b[p*temp+j].last;indegree[b[p*temp+j].last]++;
cout<<"输入以第"<<p<<"个顶点为出度的第"<<j<<"条弧的权"<<endl;
cin>>b[p*temp+j].info;
}
}
int *ve=new int[n];
for(int pp=0;pp<n;pp++)
ve[pp]=0;
int * vl=new int[n];
stack ss(n);
stack tt(n);
int ty;
for (ty=n-1;ty>=0;ty--)
if ( indegree[ty]==0 )
ss.push(ty);
int pt;
int count=0;
arc pr;
while (!ss.isEmpty())
{pt=ss.pop();
tt.push(pt);
 count++;
 for(m=0,pr=b[pt*temp+m];m<a[pt];m++,pr=b[pt*temp+m])
 {int kk=pr.last;
 if (--indegree[kk]==0) ss.push(kk);
 if(ve[pt]+pr.info>ve[kk]) ve[kk]=ve[pt]+pr.info;
}}
if(count<n) {cout<<"存在回路"<<endl;int ta=1;}
else {cout<<"已建成"<<endl;ta=0;}
if (ta) cout<<"存在回路"<<endl;
else
{for(int yy=0;yy<n;yy++)
vl[yy]=ve[yy];
int tty;
arc pk;
while (!tt.isEmpty()) 
{tty=tt.pop();
if(tty==(n-1))
vl[tty]=ve[tty];
else
for (m=0,pk=b[tty*temp+m];m<a[tty];m++,pk=b[tty*temp+m])
{int kt=pk.last; 
if((vl[kt]-pr.info)<vl[tty]) vl[tty]=vl[kt]-pk.info;
}
}
for(int jt=0;jt<n;++jt,m=0)
for(pr=b[jt*temp+m];m<a[jt];m++,pr=b[jt*temp+m])
{int kt=pr.last;
int ee=ve[jt]; 
int el=vl[kt]-pr.info;
char tag=(ee==el)?'*':' ';
cout<<"("<<jt<<","<<kt<<"),"<<jt<<"是关键活动"<<pr.info<<","<<tag<<endl;
}}
}