A题 电力抢修问题
2008年年初，我国发生大面积雨雪冰冻灾害，电力设施损毁严重。某县电力公司为了抢修当地受损电力线路，尽快实现与大电网的联通，共派出3个施工抢修队，分别从A，B，C三地开始施工(A，B，C三点为大电网电力供应接点)。如图，各乡镇之间距离已知，没有连接的乡镇之间由于地形等原因无法架设线路，另外由于技术设备原因，三个施工队施工进度不一样，A施工队每天可以施工10公里，B施工队每天可以施工8公里，C施工队每天可以施工16公里，每公里施工费用相同。同时，抢修指挥部提出以下几点要求：1、保证各乡镇之间电网互通；2、最大程度节省费用；3、最快时间完成施工。
请给出你认为比较合理的施工方案。
附各乡镇及施工起点之间距离(单位：公里)：
|
|
A
|
B
|
C
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
A
|
|
|
|
23
|
|
26
|
|
|
|
|
|
|
|
|
B
|
|
|
|
|
|
|
|
|
|
|
|
17
|
32
|
|
C
|
|
|
|
|
22
|
|
27
|
|
|
28
|
|
|
|
|
1
|
23
|
|
|
|
17
|
17
|
|
|
|
|
|
|
|
|
2
|
|
|
22
|
17
|
|
|
20
|
|
|
|
|
|
|
|
3
|
26
|
|
|
17
|
|
|
13
|
|
18
|
|
|
|
|
|
4
|
|
|
27
|
|
20
|
13
|
|
13
|
23
|
33
|
|
|
|
|
5
|
|
|
|
|
|
|
13
|
|
17
|
18
|
16
|
|
|
|
6
|
|
|
|
|
|
18
|
23
|
17
|
|
|
21
|
36
|
|
|
7
|
|
|
28
|
|
|
|
33
|
18
|
|
|
20
|
29
|
28
|
|
8
|
|
|
|
|
|
|
|
16
|
21
|
20
|
|
19
|
|
|
9
|
|
17
|
|
|
|
|
|
|
36
|
29
|
19
|
|
22
|
|
10
|
|
32
|
|
|
|
|
|
|
|
28
|
|
22
|
|
我们用最短路径算，只能算出各点之间的最短路径的距离和修的时间，用最小生成树，只能算出一个连通图，可是维修路径还是算不出来，最后，我们用手工模拟，终于，算出了最短时间。以上事实证明了：人工的总是比机器控制的好，还证明了：劳动者的智慧是无穷的！
以下是我们最短路径的源程序：
最小生成树的源程序：
//#include "stdafx.h"
#include "iostream.h"
#include "stdlib.h"
#define N 13
#define M 65535
int graph[N][N] = { ///test data for graph
{0,M,M,23,M,26,M,M,M,M,M,M,M},
{M,0,M,M,M,M,M,M,M,M,M,17,32},
{M,M,0,M,22,M,27,M,M,28,M,M,M},
{23,M,M,0,7,17,M,M,M,M,M,M,M},
{M,M,22,17,0,M,20,M,M,M,M,M,M},
{26,M,M,17,M,0,13,M,18,M,M,M,M},
{M,M,27,M,20,13,0,13,23,33,M,M,M},
{M,M,M,M,M,M,13,0,17,18,16,M,M},
{M,M,M,M,M,18,23,17,0,M,21,36,M},
{M,M,28,M,M,M,33,18,M,0,20,29,28},
{M,M,M,M,M,M,M,16,21,20,0,19,M},
{M,17,M,M,M,M,M,M,36,29,19,0,22},
{M,32,M,M,M,M,M,M,M,28,M,22,0}
} ;
bool select[N];
int pos[N];
void Prim() {
int i = 0;
int j = 0;
int t_i = 0;
int t_j = 0;
int tt_i = 0;
int tt_j = 0;
int p = 0;
int min = 0;
int t_min = 0;
int tt_min = 0;
int k = 0;
min = M;
for( i = 0; i < N; i++ )
{
for( j = 0; j < N; j++ )
{
if( graph[i][j] != 0 )
{
if( min > graph[i][j] )
{
min = graph[i][j];
t_i = i;
t_j = j;
}
}
}
}
select[t_i] = true;
select[t_j] = true;
pos[p++] = t_i;
pos[p++] = t_j;
cout << t_i-2 << " " << t_j-2 << endl;
for( ; p < N; p++ )
{
min = M;
tt_min = M;
for( i = 0; i < p; i++ )
{
for( j = 0; j < N; j++ )
{
if( !select[j] )
{
t_min = graph[pos[i]][j];
if( t_min < min )
{
min = t_min;
t_i = i;
t_j = j;
}
}
}
if( tt_min > min )
{
tt_min = min;
tt_i = t_i;
tt_j = t_j;
}
}
pos[p] = tt_j;
select[tt_j] = true;
cout << pos[tt_i]-2 << " " << tt_j-2 << endl;
}
}
int main(int argc, char* argv[])
{
cout << "the test graph is below: " << endl;
for( int i = 0; i < N; i++ )
{
for( int j = 0; j < N; j++ )
cout << graph[i][j] << " ";
cout << endl;
}
cout << "the mininum cost spanning tree is: " << endl;
Prim();
return 0;
}
#include"stdio.h"
#define Maxv 100
#define INF 100000
void ppath(int path[][Maxv],int i,int j)
{ int k;
k=path[i][j];
if(k==-1)return;
ppath(path,i,k);
switch(k)
{
case 0:printf("A"); break;
case 1:printf("B"); break;
case 2:printf("C"); break;
default:printf(" %d ",k-2);
}
ppath(path,k,j);
}
void Dispath(int A[][Maxv],int path[][Maxv],int n)
{ int i,j,B[Maxv][Maxv];
for(i=0;i<3;i++)
for(j=3;j<n;j++)
{ if(A[i][j]!=INF&&A[i][j]!=0)
{ printf("从%c到%d的路径为:",i+'A',j-2);
printf("%c,",i+'A');
ppath(path,i,j);
printf("%d",j-2);
if (i==0)
B[i][j]=A[i][j]/10;
else{ if (i==1)
B[i][j]=A[i][j]/8;
else B[i][j]=A[i][j]/16;}
printf("路径长度为:%d,所用时间为:%d\n",A[i][j],B[i][j]);
}
}
}
void Flofd(int A[][Maxv],int n)
{ int i,j,k,path[Maxv][Maxv];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
path[i][j]=-1;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>A[i][k]+A[k][j])
{ A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
Dispath(A,path,n);
}
int main()
{ int n=13,path[Maxv][Maxv];
int A[][Maxv]={{0,INF,INF,23,INF,26,INF,INF,INF,INF,INF,INF,INF},
{INF,0,INF,INF,INF,INF,INF,INF,INF,INF,INF,17,32},
{INF,INF,0,INF,22,INF,27,INF,INF,28,INF,INF,INF},
{23,INF,INF,0,7,17,INF,INF,INF,INF,INF,INF,INF},
{INF,INF,22,17,0,INF,20,INF,INF,INF,INF,INF,INF},
{26,INF,INF,17,INF,0,13,INF,18,INF,INF,INF,INF},
{INF,INF,27,INF,20,13,0,13,23,33,INF,INF,INF},
{INF,INF,INF,INF,INF,INF,13,0,17,18,16,INF,INF},
{INF,INF,INF,INF,INF,18,23,17,0,INF,21,36,INF},
{INF,INF,28,INF,INF,INF,33,18,INF,0,20,29,28},
{INF,INF,INF,INF,INF,INF,INF,16,21,20,0,19,INF},
{INF,17,INF,INF,INF,INF,INF,INF,36,29,19,0,22},
{INF,32,INF,INF,INF,INF,INF,INF,INF,28,INF,22,0}};
Flofd(A,n);
}
