📄 xunlu2hi.cpp
字号:
#include "iostream.h"
#include<stdio.h>
#include<conio.h>
#define M 17
#define M1 53
#define large 10000
#define NN 150000
#define MAX 10000.0
float d[M1][M1];
unsigned char P[M1][M1][15];
int num[M1][M1];
float simple(float **a)
{int k1 ,k2;
float r,r1,rr=0;
for(k1=0;k1<M;k1++)
{r=a[k1][0];
for(k2=1;k2<M;k2++)
if(a[k1][k2]<r)r=a[k1][k2];
if(r!=large)
{rr=rr+r;
for(k2=0;k2<M;k2++)
if(a[k1][k2]!=large)a[k1][k2]-=r;
}
}
for(k1=0;k1<M;k1++)
{r1=a[0][k1];
for(k2=1;k2<M;k2++)
if(a[k2][k1]<r1)r1=a[k2][k1];
if(r1!=large)
{rr=rr+r1;
for(k2=0;k2<M;k2++)
if(a[k2][k1]!=large)a[k2][k1]-=r1;
}
}
return rr;
}
long int *use(float **a)
{ int k1 ,k2,r1,c1,r=0,c=0;
float l1[M],l2[M],l=-1;
long int *p,p1[2];
for(k1=0;k1<M;k1++)
{ l1[k1]=a[k1][0];r1=-1;
for(k2=0;k2<M;k2++)
if(a[k1][k2]==0)
if(r1==-1) r1=0;
else {l1[k1]=0;break;}
else if(a[k1][k2]<l1[k1])
{l1[k1]=a[k1][k2];}
}
for(k2=0;k2<M;k2++)
{l2[k2]=a[0][k2];c1=-1;
for(k1=0;k1<M;k1++)
if(a[k1][k2]==0)
if(c1==-1)c1=0;
else {l2[k2]=0;break;}
else if(a[k1][k2]<l2[k2])
{l2[k2]=a[k1][k2];}
}
for(k1=0;k1<M;k1++)
for(k2=0;k2<M;k2++)
if(a[k1][k2]==0&&(l1[k1]+l2[k2]>l))
{r=k1;c=k2;l=l1[k1]+l2[k2];}
p1[0]=r;p1[1]=c;
p=p1;
return p;
}
void main()
{FILE *pp=fopen("E:\\共享资料库\\temp\\distance.doc","r");
long int i,j,k1,k2,k,E,N,ans,x,*p,k3,k4,k5,y;
//int bb[53]={50,38,2,3,39,4,5,6,7,8,40,9,41,10,11,42,12,43,13,14,15,44,45,16,17,18,19,46,20,21,47,48,22,23,24,49,25,26,27,28,51,53,29,52,30,31,32,33,34,35,36,37,1};
int gama=0,*cen,*ET1[2],**ET,vv[M][2];
// int bb[53]={50,38,2,3,39,4,5,6,47,19,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};//
//int bb[53]={50,38,3,39,4,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,2,5,6,47,19,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};
//int bb[53]={50,38,3,39,4,8,40,9,41,10,42,12,43,14,15,44,16,17,22,23,24,49,26,51,2,5,6,47,19,45,7,11,13,18,46,20,21,48,25,27,28,53,29,52,30,31,32,33,34,35,36,37,1};//
//int bb[53]={50,38,2,3,39,4,5,6,47,19,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};//
int bb[53]={50,38,3,39,4,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,2,5,6,47,19,45,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};
// int bb[53]={50,2,3,39,4,5,6,47,19,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,20,21,48,22,23,24,49,25,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,38,1};//
//2,3kuai int bb[53]={50,2,3,39,4,5,6,47,19,45,7,8,40,9,41,10,11,42,12,43,13,14,15,44,16,17,18,46,20,21,48,22,23,24,49,25,50,26,51,27,28,53,29,52,30,31,32,33,34,35,36,37,1};//
//int bb[53]={50,3,7,27,39,4,5,6,17,53,29,31,8,20,40,9,41,52,30,10,11,42,12,38,2,28,43,13,14,15,44,47,19,16,45,18,46,21,48,22,23,24,49,25,26,51,32,33,34,35,36,37,1};//
long int *parent,*L;
float *C,*r,U,xia,**A[NN],**A3,**A4,*A1,*A2,r1;
int v1,v2,dump;
float dis;
int n=M1;
int l,m;
C=new float[NN];
r=new float[NN];
parent=new long int[NN];
cen=new int[NN];
L=new long int[NN];
ET1[0]=new int[NN];
ET1[1]=new int[NN];
ET=ET1;
// ET=new long int*[NN];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i==j) { d[i][j]=0.0;num[i][j]=0; }
else
{
d[i][j]=MAX+1.0;
}
}
for(i=0;i<91;i++)
{
fscanf(pp,"%c%d,%d,%f%c",&dump,&v1,&v2,&dis,&dump);
fscanf(pp,"%c%d,%d,%f%c",&dump,&v1,&v2,&dis,&dump);
d[v1-1][v2-1]=d[v2-1][v1-1]=dis;
if(d[v1-1][v2-1]<MAX)
{
P[v1-1][v2-1][0]=v1;P[v1-1][v2-1][1]=v2;num[v1-1][v2-1]=2;
P[v2-1][v1-1][0]=v2;P[v2-1][v1-1][1]=v1;num[v2-1][v1-1]=2;
}
}
fclose(pp);
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i][k]+d[k][j]<d[i][j])
{
d[i][j]=d[i][k]+d[k][j];
num[i][j]=num[i][k]+num[k][j]-1;
for(l=0;l<num[i][k];l++) P[i][j][l]=P[i][k][l];l--;
for(m=1;m<num[k][j];m++) P[i][j][l+m]=P[k][j][m];
}
for(i=0;i<n;i++)
d[i][i]=large;
gama=36;
A3=new float*[M];
for(k1=0;k1<M;k1++)
{ A1=new float[M];
for(k2=0;k2<M;k2++)
{if(k1!=0)
if(k2!=0)A1[k2]=d[bb[k1+gama]-1][bb[k2+gama]-1];
else A1[k2]=d[bb[k1+gama]-1][bb[k2]-1];
else if(k2!=0) A1[k2]=d[bb[k1]-1][bb[k2+gama]-1];
else A1[k2]=d[bb[k1]-1][bb[k2]-1];
}
A3[k1]=A1;
}
A[0]=A3;
/*printf("The shortest distance:\n\t");
for(i=48;i<M;i++) printf("%d\t",i+1); printf("\n");
for(i=0;i<M1;i++)
{
printf("%d\t",i+1);
for(j=0;j<M1;j++) printf("%.1f\t",d[i][j]);
printf("\n");
}*/
printf("The shortest distance:\n\t");
for(i=0;i<M;i++) printf("%d\t",i+1); printf("\n");
for(i=0;i<M;i++)
{
printf("%d\t",i+1);
for(j=0;j<M;j++) printf("%.1f\t",A[0][i][j]);
printf("\n");
}
r1=simple(A[0]);
//for(k1=0;k1<M;k1++)
//parent[k1][0]=-1;
parent[0]=-1;
E=0;U=large;
k=0;cen[E]=0;
C[0]=r1;N=0;
ET[0][0]=0;ET[1][0]=0;
while(C[E]<U)
{
p=use(A[E]);
i=p[0];j=p[1];
if(i==j) cout<<"good"<<endl;
parent[N+1]=E;parent[N+2]=E;
ET[0][N+1]=i;ET[1][N+1]=j;
ET[0][N+2]=0;ET[1][N+2]=0;
if(ET[0][E]!=ET[1][E]||E==0) {cen[N+1]=cen[E]+1;cen[N+2]=cen[E]+1;}
else {cen[N+1]=cen[E];cen[N+2]=cen[E];}
// A[N+1]=copy(A[E]);A[N+2]=copy(A[E]);
A4=new float*[M];
for(k1=0;k1<M;k1++)
{
A2=new float[M];
for(k2=0;k2<M;k2++)
{A2[k2]=A[E][k1][k2];}
A4[k1]=A2;
}
A[N+2]=A4;
k1=N+1;k2=0;
vv[k2][0]=ET[0][k1];vv[k2][1]=ET[1][k1];
while(parent[k1]!=0)
{k1=parent[k1];
if(ET[0][k1]!=ET[1][k1])
{k2++;vv[k2][0]=ET[0][k1];vv[k2][1]=ET[1][k1];}
}
k3=0;y=0;
for(k1=0;k1<=k2;k1++)
{k3=vv[k1][0];k4=vv[k1][1];
x=1;
while(x)
{for(k5=k1+1;k5<=k2;k5++)
if(vv[k5][0]==k4)
{k4=vv[k5][1];break;}
if(k5>k2) x=0;
}
if(k4==k3) y=1;
}
//if(ET[0][N+1]==0||ET[1][N+1]==0)
// k2++;
if(y==1&&cen[N+1]!=M) L[++k]=-1;
else
{
A3=new float*[M];
for(k1=0;k1<M;k1++)
{
A1=new float[M];
for(k2=0;k2<M;k2++)
{A1[k2]=A[E][k1][k2];}
A3[k1]=A1;
}
A[N+1]=A3;
for(k1=0;k1<M;k1++)
{ A[N+1][i][k1]=large;
A[N+1][k1][j]=large;
}
A[N+1][j][i]=large;
r[N+1]=simple(A[N+1]);
C[N+1]=C[E]+r[N+1];
if(C[N+1]<U)
if(cen[N+1]==M)
{U=C[N+1];
ans=N+1;
}
// else
// {L[++k]=N+1;}//add
L[++k]=N+1;
}
for(k1=0;k1<M;k1++)
{delete [] A[E][k1];}
delete [] A[E];
cout<<k<<",";
A[N+2][i][j]=large;
r[N+2]=simple(A[N+2]);
C[N+2]=C[E]+r[N+2];
// if(C[N+2]<U){L[++k]=N+2;}//add k=k+1
L[++k]=N+2;
N=N+2;
k1=0;
for(x=1;x<=k;x++)
{ if(L[x]==-1) k1++;
else if(C[L[x]]>U)
{
for(k1=0;k1<M;k1++)
{delete [] A[L[x]][k1];}
delete [] A[L[x]];
L[x]=-1;
}
}
if(k1!=k)
{xia=U+1;
for(x=1;x<=k;x++)
if(L[x]!=-1&&C[L[x]]<xia)
{k1=x;xia=C[L[x]];}
L[k1]=-1;E=k1;
}
else C[E]=large;
}
//cout<<20.9+8.3+24+15.2+19.1<<endl;
cout<<k<<",";
cout<<"Least cost="<<U<<endl;
while(ans!=-1)
{
if(ET[0][ans]!=ET[1][ans]) //cout<<bb[ET[0][ans]+gama]<<"--"<<bb[ET[1][ans]+gama]<<",";
{
if(ET[0][ans]==0)
cout<<bb[ET[0][ans]];
else cout<<bb[ET[0][ans]+gama];
cout<<"--";
if(ET[1][ans]==0)cout<<bb[ET[1][ans]];
else cout<<bb[ET[1][ans]+gama];
cout<<",";
}
ans=parent[ans];
}
//getch();
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -