海底管道问题

来源:百度知道 编辑:UC知道 时间:2024/05/24 15:51:30
某石油公司在海湾拥有几个石油钻井平台,每个平台开采出的石油需要运往海岸上的炼油厂。要在平台与炼油厂之间建造一个石油运输网络。问管道如何设计,才能使成本最低?下图给出了钻井平台及炼油厂(图的顶点),并给出了经过勘测之后可能的管道铺设走向和建设费用。

#include <stdio.h>
#define null 20
typedef struct{
int toName;
int huafei;
}node;
node lujing[11][4]={{{1,2},{8,8},{7,1},{null,0}},//a-0//由于20远大于我们的元素集,
{{0,2},{2,1},{8,6},{null,0}},//b-1//所以而是代表没有,当然其权值也是没有了
{{2,1},{3,2},{9,3},{null,0}},//c-2//a-0是指数组下标所对应的元素
{{2,2},{4,9},{10,7},{null,0}},//d-3
{{3,9},{10,2},{5,4},{null,0}},//e-4
{{4,4},{10,1},{6,1},{null,0}},//f-5
{{5,1},{7,9},{9,4},{null,0}},//g-6
{{6,9},{8,7},{0,1},{null,0}},//h-7
{{0,8},{1,6},{9,1},{7,7}},//i-8
{{8,1},{2,3},{10,6},{6,4}},//j-9
{{9,6},{3,7},{4,2},{5,1}},};//k-10//其实就是一个三维数组~~

int cunzai[12]={1,0};//~[0]储存拥有元素的个数,~[1+]储存各个元素的对应下标~//a默认存在~

int biaojibian[10][3]={0,0};//~[0][0]代表本数组中共有多少有效变量~~[i][0]一个顶点~[i][1]权值~[i][2]另一个顶点~

int zaifou(int a){//传入一个数(顶点),看看他是否在这个集合里,在返回1,不在返回0,并存入~
int i,t=0;
for(i=1;i<=cunzai[0];i++)
{
i