管道铺设施工的最佳方案选择的程序怎么搞?
N(>10)个居民区之间需要铺设煤气管道,假设任意两个居民区之间都可以铺设煤气管道,但是代价不同.事先将任意两个居民区之间铺设管道的代价存入磁盘文件中,设计一个最佳方案使得这N个居民区之间铺设管道所需的代价最少
帮我看看还缺什么!还有主函数怎么写呀
#include<iostream.h>
#include<stdlib.h>
//边集数组
struct edge{
int fromvex;
int endvex;
int weight;
};
typedef edge edgeset[MaxEdgeNum];
void Create(vexlist GV,edgeset GE,int n,int e)
{
int i,k,j,w;
cout<<"输入"<<n<<"个顶点"<<endl;
for(i=0;i<n;i++)
cin>>GV[i];
cout<<"输入"<<e<<"条边"<<endl;
for(k=0;k<e;k++){
cin>>i>>j>>w;
GE[k].fromvex=i;
GE[k].endvex=j;
GE[k].weight=w;
}
}
//Prim算法
void Prim(adjmatrix GA，edgeset CT,int n)
{
int i,j,k,min,t,m,w;
for(i=0;i<n-1;i++)
{
CT[i].fromvex=0;
CT[i].endvex=i+1;
CT[i].weight=GA[0][i+1];
}
for(k=1;k<n;k++)
{
min=MaxValue;
m=k-1;
for(j=k-1;j<n-1;j++)
{
if(CT[j].weight<min){
min=CT[j].weight;
m=j;
}
edge temp=CT[k-1];
CT[k-1]=CT[m];
CT[m]=temp;
j=CT[k-1].endvex;
}
for(i=k;i<n-1;i++)
{
t=CT[i].endvex;
w=GA[j][t];
if(w<CT[i].weight){
CT[i].weight=w;
CT[i].fromvex=j;
}
}
}
}
//文件的打开与关闭
void Megfile(FILE *fp)
{
char *s;
char t[5];
fp=fopen("data.txt","w+t")
fwrite(&s,sizeof(char),5,fp)
fclose(fp);
fp=fopen("data.txt","w+t");
while(!feof(fp))
{fread(t,sizeof(char),5,fp);
printf("%s\n",t);
}
fclose(fp);
}
问题点数：60、回复次数：10Top
1 楼Riemann（）回复于 2003-09-02 22:16:49 得分 40
starfish的
#include <cstdio>
#include <cassert>
#include <cstdlib>
#define input "Prim.in" //Input file name
#define output "Prim.out" //Output file name
#define infinity 1000000 // a big int
#define max_N 100 // the max count of vertexes
typedef int Graph[max_N][max_N]; //use adjacent matrix to represent graph
FILE *fin,*fout;
int probN=0,n;
Graph G;
int read_case()
{
int i,j,k,m,w;
fscanf(fin,"%d %d",&n,&m);
if (n==0) return 0;
probN++;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
G[i][j]=infinity; //initialize the graph
for (k=0;k<m;k++)
{
fscanf(fin,"%d %d %d\n",&i,&j,&w);
G[i-1][j-1]=G[j-1][i-1]=w; //the vertexes in the input file are labed from 1 to n
}
return 1;
}
void prim(Graph G,int vcount,int father[])
{
int i,j,k;
int lowcost[max_N],closeset[max_N],used[max_N];
for (i=0;i<vcount;i++)
{
lowcost[i]=G[0][i];
closeset[i]=0; //notice: here vertex 1 is G[0]
used[i]=0; //mark all vertexes have not been used
father[i]=-1; // that means no father
}
used[0]=1; // mark vertex 1 has been used
for (i=1;i<vcount;i++)
{
j=0;
while (used[j]) j++;
for (k=0;k<vcount;k++)
if ((!used[k])&&(lowcost[k]<lowcost[j])) j=k; //find the next tree edge
father[j]=closeset[j]; //record the tree edge using father array
used[j]=1; //mark vertex j+1 has been used
for (k=0;k<vcount;k++)
if (!used[k]&&(G[j][k]<lowcost[k])) //modify the lowcost
{
lowcost[k]=G[j][k];
closeset[k]=j;
}
}
}
void solve_case()
{
int i;
int father[max_N];
fprintf(fout,"Case %d\n",probN);
prim(G,n,father);
for (i=0;i<n;i++)
fprintf(fout,"(%d,%d)\n",father[i]+1,i+1);
}
int main()
{
assert(fin=fopen(input,"r"));
assert(fout=fopen(output,"w")); //if there is no output file, comment this line
while (read_case()) solve_case();
fclose(fin);
fclose(fout); //if there is no output file, comment this line
return 0;
}Top
2 楼seanshen（南岭荔枝丹）回复于 2003-09-03 16:30:52 得分 0
谢谢,可以告诉我怎么用图形表示出来吗?
最好用c++来写程序Top
3 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2003-09-03 17:58:08 得分 20
构造一个图，点就是用户，连接权就是造价
构造一个遍历，使得权值最小。
和网络的路由选择差不多吧，DJ算法。
结果用图形表示就是把这个遍历路径画出来。Top
4 楼seanshen（南岭荔枝丹）回复于 2003-09-03 18:05:05 得分 0
DJ算法是什么呀?没有见过Top
5 楼zzwu（未名）回复于 2003-09-05 18:19:57 得分 0
这种问题应先说明N个居民的家是如何分布的？
是象城镇居民那样分布在一条街上，还是农村居民那样随意地分布在平面上？
如果同在一条街上，又再要区分：是分在街道的两边，还是集中在街道的一边？
总之，所用方法都不一样。有的很容易获得最优算法，有的则很麻烦。Top
6 楼seanshen（南岭荔枝丹）回复于 2003-09-06 12:03:56 得分 0
ft !Top
7 楼mmmcd（超超）回复于 2003-09-07 11:24:21 得分 0
你都用了最小生成树的Prim算法，还有问题么Top
8 楼seanshen（南岭荔枝丹）回复于 2003-09-07 20:15:05 得分 0
没有问题了
感谢以上所有的回答!Top
9 楼happycock（SSWW）回复于 2003-09-08 19:53:47 得分 0
happy__888([顾问团]寻开心)，不是Dijkstra算法，而是Prim算法，虽然两者形式上很像Top
10 楼zzwu（未名）回复于 2003-09-10 09:08:20 得分 0
管道铺设最优方案:
1.居民建筑分布在一条街道上,必为:
B----B-B-----B--B---B
(其中B为居民建筑,---表示管道.)
2.居民建筑分布在一条街道的2边时,则最优方案可能是:
B----B-B-----B--B---B
|
B--B-BB---B--B---BBB
但也可能是:
B----B-B-----B--B---B
| |
B--B B--BBB
还可以其他,决定于B的多少及其分布,情况就复杂了.
3.居民建筑无规则分布n点上:
B B
B B B
B B B
B B
则可用最小生成树算法,但或许还应考虑:
* 管道走线是否允许任意方向,还是必须非纵即横,不允许乱走?
* 是否要避开某些地下已经存在的其他管道位置,
等.
------------------------
Top
