数学建模钢材切割问题使用c++实现的程序

#include<iostream> #include<iomanip> #define inf 1000000 using namespace std; typedef struct vex { int x,y,z; int total; int a,b,c; }Vex; void init(Vex V[][9]) //初始化顶点信息 { int a=10,b=14,c=19; int u[6]; u[0]=6;u[1]=1;u[2]=7;u[3]=5;u[4]=9;u[5]=6; for(int i=0;i<3;i++) for(int j=0;j<9;j++) { V[i][j].x=j%3; //x表示左右表面被切割的次数； V[i][j].y=j/3; //y表示前后表面被切割的次数； V[i][j].z=i; //z表示上下表面被切割的次数； V[i][j].total=V[i][j].x+V[i][j].y+V[i][j].z; V[i][j].a=a; V[i][j].b=b; V[i][j].c=c; for(int p=0;p<V[i][j].x;p++) V[i][j].a=V[i][j].a-u[p]; for(p=0;p<V[i][j].y;p++) V[i][j].b=V[i][j].b-u[p+2]; for(p=0;p<V[i][j].z;p++) V[i][j].c=V[i][j].c-u[p+4]; } } void initweightH1(int weight[][27],Vex V[][9],int e,int r) //初始化各条边的权值 { for(int i=0;i<27;i++) for(int j=0;j<27;j++) { weight[i][j]=inf; } for (i=0;i<3;i++) for(int j=0;j<9;j++) { if(V[i][j].total<V[i][j+1].total&&j+1<9) { weight[i*9+j][i*9+j+1]=(V[i][j+1].x-V[i][j].x)*V[i][j].b*V[i][j].c; if(j==7||j==3) weight[i*9+j][i*9+j+1]=weight[i*9+j][i*9+j+1]+e; } if(V[i][j].total<V[i][j+3].total&&j+3<9) { weight[i*9+j][i*9+j+3]=(V[i][j+3].y-V[i][j].y)*V[i][j].a*V[i][j].c; if(j==4) weight[i*9+j][(i+1)*9+j]=weight[i*9+j][(i+1)*9+j]+e; } if(V[i][j].total<V[i+1][j].total&&i+1<3) weight[i*9+j][(i+1)*9+j]=(V[i+1][j].z-V[i][j].z)*V[i][j].a*V[i][j].b*r; } for (i=0;i<3;i++) { weight[i*9+1][i*9+2]=inf; weight[i*9+4][i*9+5]=inf; weight[i*9+2][i*9+5]=inf; weight[i*9+5][i*9+8]=inf; } } void initweightH2(int weight[][27],Vex V[][9],int e,int r) //初始化各条边的权值 { for(int i=0;i<27;i++) for(int j=0;j<27;j++) { weight[i][j]=inf; } for (i=0;i<3;i++) for(int j=0;j<9;j++) { if(V[i][j].total<V[i][j+1].total&&j+1<9) { weight[i*9+j][i*9+j+1]=(V[i][j+1].x-V[i][j].x)*V[i][j].b*V[i][j].c; if(j==4) weight[i*9+j][i*9+j+1]=weight[i*9+j][i*9+j+1]+e; } if(V[i][j].total<V[i][j+3].total&&j+3<9) { weight[i*9+j][i*9+j+3]=(V[i][j+3].y-V[i][j].y)*V[i][j].a*V[i][j].c; if(j==2||j==5) weight[i*9+j][(i+1)*9+j]=weight[i*9+j][(i+1)*9+j]+e; } if(V[i][j].total<V[i+1][j].total&&i+1<3) weight[i*9+j][(i+1)*9+j]=(V[i+1][j].z-V[i][j].z)*V[i][j].a*V[i][j].b*r; } for (i=0;i<3;i++) { weight[i*9+3][i*9+6]=inf; weight[i*9+4][i*9+7]=inf; weight[i*9+6][i*9+7]=inf; weight[i*9+7][i*9+8]=inf; } } int GetEdgeValue(int v0,int v2,int weight[][27]) //返回各条边的权值 { return weight[v0][v2]; } void Dijkstra(int v0,int path[],int weight[][27]) //最短路径dijkstra算法 { bool *S=new bool[27]; int *dist=new int[27]; int k; for(int i=0;i<27;i++) { dist[i]=GetEdgeValue(0,i,weight); S[i]=0; if(dist[i]<inf) path[i]=0; else path[i]=-1; } S[0]=1; dist[0]=0; for(int v=1;v<27;v++) { int min=inf; for (int j=0;j<27;j++) //找到权值最小的一条边 if(min>dist[j]&&S[j]==0) { k=j; min=dist[j]; } S[k]=1; //将该顶点加入 for(int w=0;w<27;w++) //更新集合V-S中各顶点的当前最短路径 { if(S[w]==0&&dist[k]+GetEdgeValue(k,w,weight)<dist[w]) { dist[w]=dist[k]+GetEdgeValue(k,w,weight); path[w]=k; } } } } void main() { Vex V[3][9]; int i=0; init(V); int path[2][27]={0}; int weight[27][27]; int e=2; int r=15; initweightH1(weight,V,e,r); /* for(i=0;i<27;i++) { for(int j=0;j<27;j++) cout<<setw(10)<<weight[i][j]; cout<<endl; } */ Dijkstra(0,path[0],weight); cout<<"最短路径path数组："<<endl; for(i=0;i<27;i++) cout<<setw(10)<<path[0][i]; //求费用 int behind=26; int before=path[0][behind]; int sum=0; while(before!=-1) { sum=sum+weight[before][behind]; behind=before; before=path[0][behind]; } cout<<endl<<"H1最小总费用："; cout<<sum<<"(元)"<<endl; initweightH2(weight,V,e,r); Dijkstra(0,path[1],weight); cout<<"最短路径path数组："<<endl; for(i=0;i<27;i++) cout<<setw(10)<<path[1][i]; behind=26; before=path[1][behind]; int sum1=0; while(before!=-1) { sum1=sum1+weight[before][behind]; behind=before; before=path[1][behind]; } cout<<endl<<"H2最小总费用："; cout<<sum1<<"(元)"<<endl; }