1, Purpose
1. Be familiar with the basic idea of algorithm design
2. Master the idea of minimum spanning tree algorithm
2, Content and design idea
The State Grid Corporation of China wants to lay out an EHV transmission network across the country and connect all provincial capitals. In order to reduce costs and meet some hard requirements, the State Grid plans and layout according to the following five strategies.
(1) The length of the whole power grid is required to be the shortest.
(2) It is required to minimize the length of the whole power grid when a direct dedicated line is pulled between Xining and Zhengzhou
(3) It is required to minimize the length of the whole power grid not only between Xining and Zhengzhou, but also between Hangzhou and Changsha.
(4) Under the premise that Hong Kong and Macao, Macao and Guangzhou do not pull direct lines, the length of the whole power grid is the shortest.
(5) Shandong, Henan, Shaanxi, Gansu, Qinghai, Xinjiang and other provinces farther north are called northern provinces, and the rest are called southern provinces. If only one direct line is planned between the southern and northern provinces, how to minimize the length of the whole power grid.
Please calculate the optimal situation according to these five situations.
Tips:
- If there is no special agreement, special lines can be pulled between cities, and the length is a straight line.
- The distance calculation method between any two points on the earth can refer to the following documents: https://www.cnblogs.com/ycsfwhh/archive/2010/12/20/1911232.html
Excerpts are as follows:
The earth is A nearly standard ellipsoid with an equatorial radius of 6378.140 km, an polar radius of 6356.755 km and an average radius of 6371.004 km. If we assume that the earth is A perfect sphere, then its radius is the average radius of the earth, recorded as R. If the 0-degree longitude is used as the benchmark, the surface distance between any two points on the earth's surface can be calculated according to the longitude and latitude of the two points (the error caused by the earth's surface topography is ignored here, which is only A theoretical estimate). Let the longitude and latitude of the first point A be (LonA, LatA) and the longitude and latitude of the second point B be (LonB, LatB). According to the datum of the 0-degree longitude, the positive longitude (Longitude) is taken for the east longitude, the negative longitude (- Longitude) is taken for the west longitude, the 90 latitude (90 latitude) is taken for the north latitude, and the 90 + latitude (90+Latitude) is taken for the south latitude. Then the two points after the above processing are counted as (MLonA, MLatA) and (MLonB, MLatB). Then, according to the trigonometric derivation, the following formula for calculating the distance between two points can be obtained:
C = sin(MLatA)*sin(MLatB)*cos(MLonA-MLonB) + cos(MLatA)cos(MLatB)
Distance = RArccos©*Pi/180
Here, the units of R and Distance are the same. If 6371.004 km is used as the radius, Distance is the unit of kilometer. If other units, such as mile, are used, unit conversion needs to be done. 1 km = 0.621371192mile
If only the longitude is treated as positive and negative, and the latitude is not treated as 90 latitude (assuming that it is all in the northern hemisphere and only Australia in the southern hemisphere has application significance), the formula will be:
C = sin(LatA)*sin(LatB) + cos(LatA)*cos(LatB)cos(MLonA-MLonB)
Distance = RArccos©*Pi/180
The above can be deduced through simple triangular transformation.
- The longitude and latitude of the national provincial capital cities are as follows.
city,longitude,latitude Shenyang,123.429092,41.796768 Changchun City,125.324501,43.886841 Harbin City,126.642464,45.756966 Beijing,116.405289,39.904987 Tianjin,117.190186,39.125595 Hohhot,111.751990,40.841490 Yinchuan City,106.232480,38.486440 Taiyuan City,112.549248,37.857014 Shijiazhuang City ,114.502464,38.045475 Jinan City,117.000923,36.675808 Zhengzhou City,113.665413,34.757977 Xi'an City,108.948021,34.263161 Wuhan,114.298569,30.584354 Nanjing City,118.76741,32.041546 Hefei,117.283043,31.861191 Shanghai,121.472641,31.231707 Changsha City,112.982277,28.19409 Nanchang City,115.892151,28.676493 Hangzhou,120.15358,30.287458 Fuzhou City,119.306236,26.075302 Guangzhou City,113.28064,23.125177 Taipei City,121.5200760,25.0307240 Haikou City,110.199890,20.044220 Nanning,108.320007,22.82402 Chongqing City,106.504959,29.533155 Kunming,102.71225,25.040609 Guiyang City,106.713478,26.578342 Chengdu,104.065735,30.659462 Lanzhou City,103.834170,36.061380 Xining City,101.777820,36.617290 Lhasa,91.11450,29.644150 Urumqi,87.616880,43.826630 Hong Kong,114.165460,22.275340 Macao,113.549130,22.198750
3, Use environment
C/C + + integrated compilation environment is recommended.
4, Experimental process
1. Write relevant experimental code
#include<bits/stdc++.h>
using namespace std;
#define Infinity 65535
#define ERROR -1
#define Pi 3.14
#define R 6371.004
int Index[35];
string Arr[35]={"Shenyang","Changchun","Harbin","Beijing","Tianjin","Hohhot","Yinchuan",
"Taiyuan","Shijiazhuang","Jinan","Zhengzhou","Xi'an","Wuhan","Nanjing","Hefei",
"Shanghai","Changsha","Nanchang","Hangzhou","Fuzhou","Guangzhou","Taipei","Haikou",
"Nanning","Chongqing","Kunming","Guiyang","Chengdu","Lanzhou","Xining","Lhasa",
"Urumqi","Hong Kong","Macao"};
double S[35][2]={{123.429092,41.796768},
{125.324501,43.886841},
{126.642464,45.756966},
{116.405289,39.904987},
{117.190186,39.125595},
{111.751990,40.841490},
{106.232480,38.486440},
{112.549248,37.857014},
{114.502464,38.045475},
{117.000923,36.675808},
{113.665413,34.757977},
{108.948021,34.263161},
{114.298569,30.584354},
{118.76741,32.041546},
{117.283043,31.861191},
{121.472641,31.231707},
{112.982277,28.19409},
{115.892151,28.676493},
{120.15358,30.287458},
{119.306236,26.075302},
{113.28064,23.125177},
{121.5200760,25.0307240},
{110.199890,20.044220},
{108.320007,22.82402},
{106.504959,29.533155},
{102.71225,25.040609},
{106.713478,26.578342},
{104.065735,30.659462},
{103.834170,36.061380},
{101.777820,36.617290},
{91.11450,29.644150},
{87.616880,43.826630},
{114.165460,22.275340},
{113.549130,22.198750}};
typedef struct GNode
{
int Nv;
int Ne;
double G[1000][1000];
// int Data[1000];
} MGraph;
typedef struct ENode
{
int V1,V2;
double Weight;
} Edge;
MGraph* CreateGraph(int VertexNum)
{
int V,W;
MGraph* Graph;
Graph=new MGraph;
Graph->Nv=VertexNum;
Graph->Ne=0;
for (V=0;V<Graph->Nv;V++)
{
for (W=0;W<Graph->Nv;W++)
{
Graph->G[V][W]=Infinity;
}
}
return Graph;
}
void InsertEdge(MGraph* Graph,Edge* E)
{
Graph->G[E->V1][E->V2]=E->Weight;
}
MGraph* BuildGraph(MGraph* Graph,double D[])
{
Edge* E;
int V;
int Nv,Ne,i,j,k;
k=0;
Nv=34;
Ne=1156;
Graph=CreateGraph(Nv);
Graph->Ne=Ne;
for (V=0;V<Nv;V++)
{
Index[V]=V;
}
if (Graph->Ne!=0)
{
E=new Edge;
for (i=0;i<Nv;i++)
{
for (j=0;j<Nv;j++)
{
E->V1=Index[i];
E->V2=Index[j];
E->Weight=D[k];
InsertEdge(Graph,E);
k++;
}
}
}
return Graph;
}
int FindMin(MGraph* Graph,double dist[])
{
int MinV,V;
double MinDist=Infinity;
for (V=0;V<Graph->Nv;V++)
{
if (dist[V]!=0&&dist[V]<MinDist)
{
MinDist=dist[V];
MinV=V;
}
}
if (MinDist<Infinity)
{
return MinV;
}
else
{
return ERROR;
}
}
void Print(double a[],int b[],int c[],int k,MGraph* Graph)
{
int i,j,t;
for (i=0;i<k;i++)
{
cout<<Arr[b[i]]<<"--"<<Arr[c[i]]<<": "<<a[i]<<endl;
}
}
double Prim(MGraph* Graph,MGraph* MST)
{
int k=0;
double a[10000];
int b[10000],c[10000];
double dist[10000],TotalWeight;
int parent[10000],V,W;
int VCount;
Edge* E;
for (V=0;V<Graph->Nv;V++)
{
dist[V]=Graph->G[0][V];
parent[V]=0;
}
TotalWeight=0;
VCount=0;
MST=CreateGraph(Graph->Nv);
E=new Edge;
dist[0]=0;
VCount++;
parent[0]=-1;
while(1)
{
V=FindMin(Graph,dist);
if (V==ERROR)
{
break;
}
E->V1=parent[V];
E->V2=V;
E->Weight=dist[V];
InsertEdge(MST,E);
TotalWeight+=dist[V];
dist[V]=0;
VCount++;
a[k]=E->Weight;
b[k]=E->V1;
c[k]=E->V2;
k++;
for (W=0;W<Graph->Nv;W++)
{
if (dist[W]!=0&&Graph->G[V][W]<Infinity)
{
if (Graph->G[V][W]<dist[W])
{
dist[W]=Graph->G[V][W];
parent[W]=V;
}
}
}
}
if (VCount<Graph->Nv)
{
TotalWeight=ERROR;
}
Print(a,b,c,k,Graph);
return TotalWeight;
}
int main()
{
MGraph* Graph;
MGraph* MST;
double Total;
int i,j,k;
double D[10000];
double C;
k=0;
for (i=0;i<34;i++)
{
for (j=0;j<34;j++)
{
C=sin(S[i][1]*Pi/180)*sin(S[j][1]*Pi/180)+cos(S[i][1]*Pi/180)*cos(S[j][1]*Pi/180)*cos(S[i][0]*Pi/180-S[j][0]*Pi/180);
D[k]=R*acos(C);
k++;
}
}
Graph=BuildGraph(Graph,D);
Total=Prim(Graph,MST);
cout<<Total;
return 0;
}
2. Write the idea of the algorithm.
(2) The second question is to draw a line between Xining and Zhengzhou, first connect the two cities, and then use the minimum spanning tree from Zhengzhou;
(3) On the basis of the second question, set a flag=0. When you encounter Hangzhou or Changsha, flag+1. When flag=1, skip the cycle, directly connect Hangzhou and Changsha, and then return to the cycle;
(4) On the basis of the first question, if the two end points are Hong Kong and Macao or Guangzhou and Macao, set its dist[V] to infinity, and then use the FindMin function, and the rest remain unchanged.
(5) Separate the north and south cities, use the Prim algorithm respectively, and then find the minimum value from the distance between the north and south cities. The combination of the three is the solution.
3. Output the grid data table of each group of experiments and the total length of the grid, and present it visually.