cpp1.cpp

布线问题(分支限界算法应用)

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include<stdlib.h>
struct edge
{
	int vertexposi1;   //vertex1
	int vertexposi2;   //vertex2
	double  length;       //the length of the edge
};
struct coordinate  //store the spacial coordinate of the door and the room and the room size
{
	double  x;
	double  y;
	double  z;
};
struct position
{
	struct coordinate *door;
	struct coordinate *vertex;
	struct coordinate *room;
};
struct heap
{
	int capacity;
	int size;
	struct edge *queue;
};
typedef struct heap *heappointor;
void kruskal(struct edge *edge,int edgenum,int vertexnum);
void readgraphintoheap(struct edge *edge,heappointor h);
void buildheap(heappointor h);
void percolatedown(heappointor h,int posi);
int isempty(heappointor h);
struct edge deletemin(heappointor h );
int find(int vertexposi,int s[]);
void setunion(int s[],int uset,int vset);
void insertionsort(int a[],int n);
double   findshortestpath(struct position *posi,int vertexposi1,int vertexposi2);
int whichwall(struct position *posi,int vertexposi);
double min(double a,double b);
double max(double a,double b);
double doormidx,doormidy,doormidz,doorheight,clength;

FILE *fpw;
FILE *fpr;

int main()
{
	int vertexnum,edgenum,i;
	struct edge *edge;
	struct position *posi;
	int vertexposi1,vertexposi2;
	fpr=fopen("input.txt","r");
	if(fpr==NULL)
		 printf("can't open the file!\n");
	fpw=fopen("output.txt","w");
	if(fpw==NULL)
		printf("Can't write output.txt!\n");
	posi=(struct position *)malloc(sizeof(struct position));
	if(posi==NULL)
		printf("Out of space!\n");
	posi->door =(struct coordinate *) malloc(sizeof(struct coordinate)*4);
	if(posi->door==NULL)
		printf("Out of space!\n");
	posi->room = (struct coordinate *)malloc(sizeof(struct coordinate));
	if(posi->room==NULL)
		printf("Out of space!\n");
	for(i=0;i<4;i++)
	{
		fscanf(fpr,"%lf %lf %lf",&posi->door[i].x, &posi->door[i].y, &posi->door[i].z);
	}
	doormidx=(posi->door[0].x+posi->door[1].x+posi->door[2].x+posi->door[3].x)/4-posi->door[0].x;
	doormidy=(posi->door[0].y+posi->door[1].y+posi->door[2].y+posi->door[3].y)/4-posi->door[0].y;
	doormidz=(posi->door[0].z+posi->door[1].z+posi->door[2].z+posi->door[3].z)/4-posi->door[0].z;
	doorheight=2*doormidz;
	posi->door[1].x=posi->door[0].x+2*doormidx;
	posi->door[1].y=posi->door[0].y+2*doormidy;
	posi->door[1].z=posi->door[0].z;
	fscanf(fpr,"%lf %lf %lf",&posi->room[0].x, &posi->room[0].y, &posi->room[0].z);
	clength=(posi->room[0].x+posi->room[0].y)*2;
	fscanf(fpr,"%d",&vertexnum);
	posi->vertex =(struct coordinate *)malloc(sizeof(struct coordinate)*vertexnum);
		if(posi->vertex==NULL)
			printf("Out of space!\n");
	for(i=0;i<vertexnum;i++)
	{	fscanf(fpr,"%lf %lf %lf",&posi->vertex[i].x,&posi->vertex[i].y,&posi->vertex[i].z);
	}
	edgenum=vertexnum*(vertexnum-1)/2;
	edge=(struct edge *)malloc(sizeof(struct edge)*edgenum);
	if(edge==NULL)
	printf("out of space!\n");
	i=0;
	for(vertexposi1=0;vertexposi1<vertexnum-1;vertexposi1++)
	{	for(vertexposi2=vertexposi1+1;vertexposi2<vertexnum;vertexposi2++)
			{
				edge[i].vertexposi1=vertexposi1;
				edge[i].vertexposi2=vertexposi2;
				edge[i].length= findshortestpath(posi ,vertexposi1,vertexposi2);
				i++;
			}
	}
		kruskal(edge,edgenum,vertexnum);
		free(edge);
		free(posi->vertex);
	fclose(fpr);
	fclose(fpw);
	free(posi->room);
	free(posi->door);
	free(posi);
	return 0;
}

void kruskal(struct edge *edge,int edgenum,int vertexnum)
{	int edgesaccepted=0,i;
	struct edge e;
	int *s;
	int uset,vset; 
	double  result=0;
	heappointor h;
	h=(heappointor)malloc(sizeof(struct heap));
	if(!h)
		printf("get room for the heap failed!");
	h->capacity=edgenum;
	h->size=0;
	h->queue=(struct edge *)malloc(sizeof(struct edge)*(edgenum+1));
	if(!h->queue)
		printf("out of space!\n");
	s=(int *)malloc(sizeof(int)*vertexnum);
	if(!s)
		printf("out of space!\n");
	/* initialize s */
	for(i=0;i<vertexnum;i++)
		s[i]=-1;
	readgraphintoheap(edge,h);
	buildheap(h);
	while(edgesaccepted<vertexnum-1)
	{
		e=deletemin(h);		/* get the shortest edge length */
		uset=find(e.vertexposi1,s);	  /* find vertex1 vertex2 whether have been connected */
		vset=find(e.vertexposi2,s);

		if(uset!=vset)
		{
			/* accept the edge */
			edgesaccepted++;
			setunion(s,uset,vset);	/* union two set into one set */
			result+=e.length;		/* the shortest edge length add to result */
		}
	}
	fprintf(fpw,"%.f\n", result );	/* output , using interger */
	free(h);	/* free the space */
	free(s);
}
void readgraphintoheap(struct edge *edge,heappointor h)
{
	int i;
	h->queue[0].length=0;

	/* put each queue[i] point to one edge */
	for(i=0;i<h->capacity;i++)
	{
		h->queue[i+1]=edge[i];
		h->size++;
	}
}
void buildheap(heappointor h)
{
	int posi;
	for(posi=h->size/2;posi>0;posi--)
		percolatedown(h,posi);

}
void percolatedown(heappointor h,int posi)
{
	int i,child;
	struct edge tmp;
	tmp=h->queue[posi];
	for(i=posi;i*2<=h->size;i=child)
	{
		/* find smaller child */
		child = i * 2;
		if( child !=h->size&&h->queue[child+1].length<h->queue[child].length)
			child++;
		/* percolate one level */
		if(tmp.length>h->queue[child].length)
			h->queue[i]=h->queue[child];
		else
			break; 
	}
	h->queue[i]=tmp;
}
int isempty(heappointor h)
{
	if(h->size==0)
		return 1;
	else 
		return 0;

}
struct edge deletemin(heappointor h )
{
	struct edge minedge;
	if( isempty(h) )
	{
		printf( "priority queue is empty" );
		exit(0);
		return h->queue[0];                       
	}
	minedge=h->queue[ 1 ];
	h->queue[1]=h->queue[h->size--];
	percolatedown(h,1);
	return minedge;
}
int find(int vertexposi,int s[])
{
	if(s[vertexposi]<0)	/* when s[i] is less than 0 ,it means vertex i is the root */
		return vertexposi;
	else
		return s[vertexposi]=find(s[vertexposi],s);
}
void setunion(int s[],int uset,int vset)
{
	s[uset]=vset;
}
void insertionsort(double a[],int n)
{
	int j,p;
	double tmp;
	for(p=1;p<n;p++)
	{
		tmp=a[p];
		for(j=p;j>0&&a[j-1]>tmp;j--)
			a[j]=a[j-1];
		a[j]=tmp;
	}
}
int whichwall(struct position *posi,int vertexposi)
{
	if(posi->vertex[vertexposi].y==0)
		return 1;
	if(posi->vertex[vertexposi].x==posi->room[0].x)
		return 2;
	if(posi->vertex[vertexposi].y==posi->room[0].y)
		return 3;
	if(posi->vertex[vertexposi].x==0)
		return 4;
}
double min(double a,double b)
{
	if(a>=b)
		return b;
	else
		return a;
}
double max(double a,double b)
{
	if(a>=b)
		return a;
	else
		return b;
}
double  findshortestpath(struct position *posi,int vertexposi1,int vertexposi2)
{
	int i=0;
	double  temp[4];
	double length,lengthtmp,length1,length2,lengthtmp1,lengthtmp2,mindis;
		temp[0]=fabs(posi->vertex[vertexposi1].z);
		temp[1]=fabs(posi->vertex[vertexposi1].z-doorheight);
		temp[2]=fabs(posi->vertex[vertexposi2].z);
		temp[3]=fabs(posi->vertex[vertexposi2].z-doorheight);
		insertionsort(temp,4);
		mindis=temp[0];
	if(whichwall(posi,vertexposi1)==whichwall(posi,vertexposi2))
	{	lengthtmp=fabs(posi->vertex[vertexposi1].x-posi->vertex[vertexposi2].x)+
				fabs(posi->vertex[vertexposi1].y-posi->vertex[vertexposi2].y)+
				fabs(posi->vertex[vertexposi1].z-posi->vertex[vertexposi2].z);	
		if(doorheight<=posi->vertex[vertexposi1].z||doorheight<=posi->vertex[vertexposi2].z)
			length=lengthtmp;
		if(doorheight>=posi->vertex[vertexposi1].z&&doorheight>=posi->vertex[vertexposi2].z)
		{
			if(posi->door[0].x<min(posi->vertex[vertexposi1].x,posi->vertex[vertexposi2].x)&&
				posi->door[1].x>max(posi->vertex[vertexposi1].x,posi->vertex[vertexposi2].x)||
				posi->door[0].y<min(posi->vertex[vertexposi1].y,posi->vertex[vertexposi2].y)&&
				posi->door[1].y>max(posi->vertex[vertexposi1].y,posi->vertex[vertexposi2].y))
				length=lengthtmp+2*mindis;
			else
				length=lengthtmp;
		}		
	}
	if(fabs(whichwall(posi,vertexposi1)-whichwall(posi,vertexposi2))==1||fabs(whichwall(posi,vertexposi1)-whichwall(posi,vertexposi2))==3) //the two point are in neibor
	{	lengthtmp1=fabs(posi->vertex[vertexposi1].x-posi->vertex[vertexposi2].x)+
				fabs(posi->vertex[vertexposi1].y-posi->vertex[vertexposi2].y)+
				fabs(posi->vertex[vertexposi1].z-posi->vertex[vertexposi2].z);  //the path turn in one side
		lengthtmp2=clength-lengthtmp1+2*fabs(posi->vertex[vertexposi1].z-posi->vertex[vertexposi2].z);  // the path turn in the other side
		length2=fabs(posi->vertex[vertexposi1].x-posi->vertex[vertexposi2].x)+  //go through the floor
				fabs(posi->vertex[vertexposi1].y-posi->vertex[vertexposi2].y)+
				fabs(posi->vertex[vertexposi1].z+posi->vertex[vertexposi2].z);
		if(doorheight>=posi->vertex[vertexposi1].z&&doorheight>=posi->vertex[vertexposi2].z)
		{	if(posi->door[0].x>=min(posi->vertex[vertexposi1].x,posi->vertex[vertexposi2].x)&&posi->door[1].x<=max(posi->vertex[vertexposi1].x,posi->vertex[vertexposi2].x)
				&&posi->door[0].y>=min(posi->vertex[vertexposi1].y,posi->vertex[vertexposi2].y)&&posi->door[1].y<=max(posi->vertex[vertexposi1].y,posi->vertex[vertexposi2].y)) //the door is in path 1  benyou=
			{
				length1=lengthtmp1+2*mindis;
				length=min(length1,min(lengthtmp2,length2));
			}
			else                                   //the door is in path2
			{	
				length1=lengthtmp2+2*mindis;
				length=min(length1,min(lengthtmp1,length2));	
			}
		}
		else
			length=min(lengthtmp1,min(lengthtmp2,length2));	
	}
	if(whichwall(posi,vertexposi1)==1&&whichwall(posi,vertexposi2)==3||whichwall(posi,vertexposi1)==3&&whichwall(posi,vertexposi2)==1)
	//the two points are in 1 and 3 wall
	{   lengthtmp1=	fabs(posi->vertex[vertexposi1].z-posi->vertex[vertexposi2].z)+
					posi->vertex[vertexposi1].x+posi->vertex[vertexposi2].x+
					fabs(posi->vertex[vertexposi1].y-posi->vertex[vertexposi2].y);
		lengthtmp2=clength-length1+2*fabs(posi->vertex[vertexposi1].z-posi->vertex[vertexposi2].z);
		if(posi->vertex[vertexposi1].x>=posi->door[0].x&&posi->vertex[vertexposi1].x<=posi->door[1].x
			&&posi->vertex[vertexposi2].x>=posi->door[0].x&&posi->vertex[vertexposi2].x<=posi->door[1].x)
		{
			length2=posi->vertex[vertexposi1].z+posi->vertex[vertexposi2].z+		// through the floor
				fabs(posi->vertex[vertexposi1].x-posi->vertex[vertexposi2].x)+  
				fabs(posi->vertex[vertexposi1].y-posi->vertex[vertexposi2].y)
				+2*min(min(fabs(posi->vertex[vertexposi1].x-posi->door[0].x),fabs(posi->vertex[vertexposi1].x-posi->door[1].x)),min(fabs(posi->vertex[vertexposi2].x-posi->door[0].x),fabs(posi->vertex[vertexposi2].x-posi->door[1].x)));
		}
		else
			length2=posi->vertex[vertexposi1].z+posi->vertex[vertexposi2].z+		// through the floor
				fabs(posi->vertex[vertexposi1].x-posi->vertex[vertexposi2].x)+  
				fabs(posi->vertex[vertexposi1].y-posi->vertex[vertexposi2].y);
		if(doorheight>=posi->vertex[vertexposi1].z&&doorheight>=posi->vertex[vertexposi2].z)
		{
			if(posi->door[0].x<=posi->vertex[vertexposi1].x)
			{	length1=lengthtmp1+2*mindis;
				length=min(length1,min(lengthtmp2,length2));
			}
			if(posi->door[0].x>=posi->vertex[vertexposi1].x||posi->door[1].x>=posi->vertex[vertexposi1].x)
			{
					length1=lengthtmp2+2*mindis;
				length=min(length1,min(lengthtmp1,length2));
			}
		}
		else
			length=min(lengthtmp1,min(lengthtmp2,length2));				
	}
	if(whichwall(posi,vertexposi1)==2&&whichwall(posi,vertexposi2)==4||whichwall(posi,vertexposi1)==4&&whichwall(posi,vertexposi2)==2)
	//the two points are in 2 and 4 wall
	{	lengthtmp1=	fabs(posi->vertex[vertexposi1].z-posi->vertex[vertexposi2].z)+
					posi->vertex[vertexposi1].y+posi->vertex[vertexposi2].y+
					fabs(posi->vertex[vertexposi1].x-posi->vertex[vertexposi2].x);
		lengthtmp2=clength-length1+2*fabs(posi->vertex[vertexposi1].z-posi->vertex[vertexposi2].z);

		if(posi->vertex[vertexposi1].y>=posi->door[0].y&&posi->vertex[vertexposi1].y<=posi->door[1].y
			&&posi->vertex[vertexposi2].y>=posi->door[0].y&&posi->vertex[vertexposi2].y<=posi->door[1].y)
		{
			length2=posi->vertex[vertexposi1].z+posi->vertex[vertexposi2].z+		// through the floor
				fabs(posi->vertex[vertexposi1].x-posi->vertex[vertexposi2].x)+  
				fabs(posi->vertex[vertexposi1].y-posi->vertex[vertexposi2].y)
				+2*min(min(fabs(posi->vertex[vertexposi1].y-posi->door[0].y),fabs(posi->vertex[vertexposi1].y-posi->door[1].y)),min(fabs(posi->vertex[vertexposi2].y-posi->door[0].y),fabs(posi->vertex[vertexposi2].y-posi->door[1].y)));
		}
		else
			length2=posi->vertex[vertexposi1].z+posi->vertex[vertexposi2].z+		// through the floor
				fabs(posi->vertex[vertexposi1].x-posi->vertex[vertexposi2].x)+  
				fabs(posi->vertex[vertexposi1].y-posi->vertex[vertexposi2].y);

		if(doorheight>=posi->vertex[vertexposi1].z&&doorheight>=posi->vertex[vertexposi2].z)
		{
			if(posi->door[0].y<=posi->vertex[vertexposi1].y)
			{	length1=lengthtmp1+2*mindis;
				length=min(length1,min(lengthtmp2,length2));
			}
			if(posi->door[0].y>=posi->vertex[vertexposi1].y||posi->door[1].y>=posi->vertex[vertexposi1].y)
			{
					length1=lengthtmp2+2*mindis;
				length=min(length1,min(lengthtmp1,length2));
			}
		}
		else
			length=min(lengthtmp1,min(lengthtmp2,length2));				
	}
	return length;	
}