oil.cpp

采用分治算法而编写的输油管道最短路径问题.

#include<iostream>
#include<cmath>
using namespace std;
#include<stdio.h>

int partition(int num[],int left,int right)//计算中心点的下标
{
	int pivot;//存储中心点的值
	pivot=num[left];
	while(left<right)
	{
		while(num[right]>=pivot&&left<right)//从右向左扫描：跳过较大的或相等的值
	    right--;
	    if(right!=left)
	{
		num[left]=num[right];
		left++;
	}
	while(num[left]<=pivot&&left<right)//从左向右扫描：跳过较小的或相等的值
		left++;
	if(right!=left)
	
	{num[right]=num[left];
	right--;
	}
	}
	num[left]=pivot;
	return left;//返回中心点下标
}

void quicksort(int num[],int low,int high)//快速排序具体实现
{
	int pivot;
	pivot=partition(num,low,high);//对序列进行分割
	if(low<pivot)
		quicksort(num,low,pivot-1);//对左子序列进行快速排序
	if(high>pivot)
		quicksort(num,pivot+1,high);//对右子序列进行快速排序
}

void main()
{ 
	int i,n,minlength=0;
	int x[100],y[100];             //存储各个管道的x、y坐标
    FILE *fp,*fp1;  
	fp=fopen("input.txt","r");     //打开输入文件
    fscanf(fp,"%d",&n);           //从文件中读出油井个数
    cout<<"油井个数为:"<<n<<endl<<endl;

    for(i=0;i<n;i++)
	{
		fscanf(fp,"%d",&x[i]);     //从文件中读出管道的x坐标
        fscanf(fp,"%d",&y[i]);     //从文件中读出管道的y坐标
		cout<<"第"<<i+1<<"个管道的x、y坐标:"<<x[i]<<"\t"<<y[i]<<endl;
	}

	quicksort(y,0,n-1);            //通过快速排序将数据从小到大排列
	cout<<"\n主管道的最优位置为y="<<y[n/2]<<endl;//输出主管道最优位置

	for(i=0;i<n;i++)
		minlength+=abs(y[i]-y[n/2]);//求得油井到主管道间的输油管道最小长度
        cout<<"\n油井到主管道间的输油管道最小长度总和："<<minlength<<endl;

		fp1=fopen("output.txt","w");//打开输出文件
		fprintf(fp1,"%d",minlength);
		cout<<"\n并将结果保存到当前文件夹的output.txt文件里"<<endl<<endl;
		fclose(fp1);
		fclose(fp);
}