數據結構_課程設計――最小生成樹：室內布線
來源：程序員人生 發布時間：2014-09-08 07:12:09 閱讀次數：2757次
***************************************轉載請注明出處：http://blog.csdn.net/lttree********************************************
這道課程設計，費不少時間，太麻煩了= =。（明明是能力不夠
）
~~~~最小生成樹：室內布線~~~~
題目要求：
裝修新房子是一項頗為復雜的工程，現在需要寫個程序幫助房主設計室內電線的布局。
首先，墻壁上插座的位置是固定的。插座間需要有電線相連，而且要布置的整齊美觀，即要求每條線都與至少一條墻邊平行，且嵌入四壁或者地板（不能走屋頂）。
房主要求知道，要將所有插座連通，自己需要買的電線的最短長度。
另外，別忘了每個房間都有門，電線不可以穿門而過。上圖給出了一個有4插座的房間的電線布局。
輸入要求：
輸入由若干組測試數據組成。
每組數據的第1行包含房間的長、寬、高和插座的個數N（N為一個不超過20的正整數）。
接下去的N行中，第i行給出第i個插座的位置坐標（xi,yi,zi）；最后一行包含4個3元組（x1,y1,z1）…（x4，y4，z4），分別是長方形門框的4個角三維坐標。4個數字全部為0表示全部測試結束，不要對該數據任何處理。
注意：這里假設長方體形狀的房間完全位于三維直角坐標系的第一象限內，并且有一個角落在原點上。地板位于x-y平面。題目數據保證，每個插座僅屬于四面墻中的一面，門上沒有插座。要求每段電線的兩端必須僅與插座連接，電線之間不能互相交叉焊接。
輸出要求：
對每一組測試，在一行里輸出要將所有插座連通需要買的電線的最短整數長度。
輸入例子：
10 10 10 4
0 1 3.3
2.5 0 2
5 0 0.8
5 10 1
0 0 0 0 0 3 1.5 0 0 1.5 0 3
0 0 0 0
輸出例子：
21
這道題，注意以下幾點：
① 布線要與墻平行
② 兩插座位置關系
③ 線可以走地面，不可以走屋頂和門
④ 最后數據，向上取整
然后，題目考查的是最小生成樹，但我花了很多時間求兩插座之間的距離= =。。
我代碼注釋中出現的 1,2,3,4 4個面為：正對著我們的為 1號面，我們正對著1號面，它的左面為2號面，1號面右面為3號面，1號面相對著4號面。
然后，程序是：
/*******************************************
********************************************
* Author:Tree *
* From : blog.csdn.net/lttree *
* Title : 最小生成樹：室內布線 *
* Source: 數據結構_課程設計 *
* Hint : 最小生成樹 *
********************************************
*******************************************/
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
/****** 一些相關變量的定義 ******/
// 插座個數，最多為20個，所以，邊最多只有400個
#define MAX 401
// 點的結構體
struct Node
{
double x,y,z;
}nd[21],door[4];
// 含權值的邊的結構體
struct Edge
{
int u;
int v;
double quan;
}eg[MAX];
// N - 插座個數，len,wid,hei - 房間的長、寬、高，pos_door門所在位置
int N,len,wid,hei,pos_door;
int father[21];
/****** 判斷兩插座位置關系 ******/
// 是否在同一墻面
bool isTogether( Node a , Node b )
{
if( (a.x==b.x && (a.x==0||a.x==len) ) || (a.y==b.y && (a.y==0||a.y==wid) ) ) return true;
return false;
}
// 判斷是否在相鄰墻面
bool isBeside( Node a , Node b )
{
if( a.x==0 || a.x==len )
{
if( b.y==0 || b.y==wid )
return true;
else
return false;
}
else if( a.y==0 || a.y==wid )
{
if( b.x==0 || b.x==len )
return true;
else
return false;
}
}
// 是否在相對墻面
bool isAcross( Node a , Node b )
{
if( (a.x==0 && b.x==len) || (a.y==0 && b.y==wid) || (a.x==len && b.x==0) || (a.y==wid && b.y==0) )
return true;
else
return false;
}
/****** 一系列判斷 ******/
// 求最小值
double Min( double a,double b)
{
return a<b?a:b;
}
// 判斷門在哪個墻面
int judge_d( Node d[] )
{
if( d[0].y==0 && d[3].y==0 ) return 1;
else if( d[0].x==0 && d[3].x==0 ) return 2;
else if( d[0].x==len && d[3].x==len ) return 3;
else if( d[0].y==wid && d[3].y==wid ) return 4;
}
// 判斷兩個同墻插座間連線是否穿門
bool judge_crossdoor( Node n1, Node n2 )
{
// 如果插座在最下面，或者插座位置高于門的位置，則不穿過門（無論墻和插座位置關系如何）
if( n1.z==0 || n2.z==0 || n1.z>=door[3].z || n2.z>=door[3].z ) return false;
if( pos_door==1 )
{
if( n1.y!=0 && n2.y!=0 ) return false;
if( (n1.x>=door[3].x && n2.x>=door[3].x) || (n1.x<=door[0].x && n2.x<=door[0].x) ) return false;
return true;
}
else if( pos_door==2 )
{
if( n1.x!=0 && n2.x!=0 ) return false;
if( (n1.y<=door[0].y && n2.y<=door[0].y) || (n1.y>=door[3].y && n2.y>=door[3].y) ) return false;
return true;
}
else if( pos_door==3 )
{
if( n1.x!=len && n2.y!=len ) return false;
if( (n1.y<=door[0].y && n2.y<=door[0].y) || (n1.y>=door[3].y && n2.y>=door[3].y) ) return false;
return true;
}
else
{
if( n1.y!=wid && n2.y!=wid ) return false;
if( (n1.x>=door[3].x && n2.x>=door[3].x) || (n1.x<=door[0].x && n2.x<=door[0].x) ) return false;
return true;
}
}
/****** 求布線長度 ******/
// 求同墻兩插座最短布線
double find_togcost( Node a,Node b )
{
// 兩插座同墻且不穿門
if( !judge_crossdoor( a , b ) )
return (fabs(a.x-b.x)+fabs(a.y-b.y)+fabs(a.z-b.z));
else
{
// 兩插座布線會穿過門，門的位置不同
if( pos_door==1 || pos_door==4 ) return Min( (fabs(a.x-b.x)+fabs(door[3].z-a.z)+fabs(door[3].z-b.z) ),(fabs(a.x-b.x)+a.z+b.z) );
else return Min( (fabs(a.y-b.y)+fabs(door[3].z-a.z)+fabs(door[3].z-b.z)),(fabs(a.y-b.y)+a.z+b.z) );
}
}
// 求相對墻兩插座最短布線
double find_acrcost( Node a,Node b )
{
double cost1,cost2;
Node temp1,temp2;
// 插座在1,4面
if( (a.y==0 && b.y==wid) || (b.y==0 && a.y==wid) )
{
// 根據門的位置，求權值
if( pos_door==1 ) return Min( Min( (a.y+fabs(door[3].z-a.z)+len+b.y),(a.y+a.z+len+b.y) ),Min( (wid-a.y+len+wid-b.y),(a.z+len+b.z) ) );
else if( pos_door==2 )
{
temp1=temp2=a;
temp1.y=0,temp2.y=wid;
cost1=find_togcost(a,temp1);
cost2=find_togcost(a,temp2);
return Min( (cost1+len+b.y),(cost2+len+wid-b.y) );
}
else if( pos_door==3 )
{
temp1=temp2=b;
temp1.y=0,temp2.y=wid;
cost1=find_togcost(b,temp1);
cost2=find_togcost(b,temp2);
return Min( (cost1+len+a.y),(cost2+len+wid-a.y) );
}
else return Min( Min( (a.y+len+b.y),(wid-a.y+wid-b.y+fabs(door[3].z-a.z)+len) ), Min( (wid-a.y+wid-b.y+a.z+len),(a.z+b.z+len) ) );
}
else
{
if( pos_door==1 )
{
temp1=temp2=a;
temp1.x=0,temp2.x=len;
cost1=find_togcost(a,temp1);
cost2=find_togcost(a,temp2);
return Min( (cost1+wid+b.x),(cost2+wid+len-b.x) );
}
else if( pos_door==2 ) return Min( Min( (a.x+b.x+wid+fabs(door[3].z-a.z)),(a.x+b.x+wid+a.z) ),Min( (len-a.x+len-b.x+wid),(a.z+b.z+wid) ) );
else if( pos_door==4 )
{
temp1=temp2=b;
temp1.x=0,temp2.x=len;
cost1=find_togcost(b,temp1);
cost2=find_togcost(b,temp2);
return Min( (cost1+wid+a.x),(cost2+wid+len-a.x) );
}
else return Min( Min( (a.x+b.x+wid),(a.z+b.z+wid) ),Min( (len-a.x+len-b.x+fabs(door[3].z-a.z)+wid),(len-a.x+len-b.x+a.z+wid) ) );
}
}
// 求相鄰墻兩插座最短布線
double find_bescost( Node a , Node b )
{
Node temp=a;
// 在兩平面連接處找一個點（讓其中一點x,y為0即可），轉化為兩個 同墻插座 問題
if( (a.x==0 && b.y==0) || (b.x==0 && a.y==0) )
{
temp.x=temp.y=0;
return ( find_togcost(a,temp)+find_togcost(b,temp) );
}
else if( (a.x==len && b.y==0) || (a.y==0 && b.x==len) )
{
temp.x=len,temp.y=0;
return ( find_togcost(a,temp)+find_togcost(b,temp) );
}
else if( (a.x==0 && b.y==wid) || (b.x==0 && a.y==wid) )
{
temp.x=0,temp.y=wid;
return ( find_togcost(a,temp)+find_togcost(b,temp) );
}
else
{
temp.x=len,temp.y=wid;
return ( find_togcost(a,temp)+find_togcost(b,temp) );
}
}
/****** 求最小生成樹(Kruscal) ******/
// 比較函數
bool cmp(Edge e1,Edge e2)
{
return e1.quan<e2.quan;
}
// 并查集 初始化函數
void Init( int m )
{
int i;
for(i=1;i<=m;i++)
father[i]=i;
}
// 并查集 查找函數
int Find(int x)
{
while(father[x]!=x)
x=father[x];
return x;
}
// 并查集 合并函數
void Combine(int a,int b)
{
int temp_a,temp_b;
temp_a=Find(a);
temp_b=Find(b);
if(temp_a!=temp_b)
father[temp_a]=temp_b;
}
// 最小生成樹 Kruskal 算法
double Kruskal( int n )
{
Edge e;
int i;
double res;
sort(eg,eg+n,cmp);
// 并查集 初始化
Init(N);
// 構建最小生成樹
res=0;
for( i=0;i<n;++i )
{
e=eg[i];
if( Find(e.u)!=Find(e.v) )
{
Combine(e.u,e.v);
res+=e.quan;
}
}
return res;
}
/****** 主函數 ******/
void main()
{
// i,j 為中間變量，k為邊的個數
int i,j,k;
while( cin>>len>>wid>>hei>>N )
{
// 輸入數據為4個0，則退出程序
if( !len && !wid && !hei && !N ) break;
// 獲取數據（插座與門的位置）
for( i=0 ; i<N ; ++i )
cin>>nd[i].x>>nd[i].y>>nd[i].z;
for( i=0 ; i<4 ; ++i )
cin>>door[i].x>>door[i].y>>door[i].z;
pos_door=judge_d( door );
/* 求兩點間距離（注意，布線要與墻平行） */
k=0;
for( i=0 ; i<N ; ++i )
{
for( j=i+1; j<N ; ++j )
{
eg[k].u=i;
eg[k].v=j;
// 判斷兩點關系，同墻or相鄰墻or相對墻
// 同墻
if( isTogether( nd[i] , nd[j] ) ) eg[k].quan=find_togcost(nd[i],nd[j]);
// 相對墻
else if( isAcross( nd[i] , nd[j] ) ) eg[k].quan=find_acrcost(nd[i],nd[j]);
// 相鄰墻
else eg[k].quan=find_bescost(nd[i],nd[j]);
++k;
}
}
/* 用Kruscal算法求最小生成樹 */
// 注意最后，無論長度如何，都要向上取整
double cost;
cost=Kruskal(k);
if( cost-int(cost)==0 ) cout<<cost<<endl;
else cout<<int(cost+1)<<endl;
}
}
***************************************轉載請注明出處：http://blog.csdn.net/lttree********************************************
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
