#include "stdio.h"
#include "malloc.h"
#include "math.h"

void CRAFT(int N, struct point *P, double *F, int *S);

#define EPS (10E-1)
#define s(k)	(*(S+k))
#define t(k)	(*(T+k))
#define f(i, j)	(*(F+i*N+j))
#define px(k)	((P+k)->x)
#define py(k)	((P+k)->y)
#define d(i, j)	(fabs(px(j)-px(i)) + fabs(py(j)-py(i)))

typedef struct point
{
	double x;
	double y;
}point;

void main()
{
	int N, i, j;
	point *P;
	double *F;
	int *S, ss;
	float x1, y1;
	FILE *fp;
	char fn[80];

	printf("\n請輸入文件名:");
	scanf("%s", fn);
	fp = fopen(fn, "r");

	fscanf(fp, "%d", &N);
	P = (point *)malloc(sizeof(point) * N);
	F = (double *)malloc(sizeof(double) * N * N);
	S = (int *)malloc(sizeof(int) * N);

	for (i = 0; i < N; i++)
	{
		fscanf(fp, "%f%f", &x1, &y1);
		px(i) = x1;
		py(i) = y1;
	}

	for (i = 0; i < N; i++)	
	{
		for (j = 0; j < N; j++)
		{
			fscanf(fp, "%f", &x1);
			f(i, j) = x1;
		}
	}

	printf("\n布置地點坐標:\n");
	for (i = 0; i < N; i++)	
	{
		printf("(%d, %d), ", (int)px(i), (int)py(i));;
	}

	printf("\n運費:\n");
	for (i = 0; i < N; i++)	
	{
		for (j = 0; j < N; j++)
		{
			printf("%10.3f", f(i, j));;
		}
		printf("\n");
	}

	printf("\n請輸入初始布置方案:\n");
	for (i = 0; i < N; i++)
	{
		printf("地點P%-2d:安排設備t", i+1);
		scanf("%d", &ss);
		s(i) = ss - 1;
	}

	CRAFT(N, P, F, S);

	free(S);
	free(F);
	free(P);
	getch();
}

double zf(int N, point *P, double *F, int *S)
{
	int i, j;
	double z = 0.0;

	for (i = 0; i < N - 1; i++)
	{
		for (j = i+1; j < N; j++)
		{
			z += (f(s(i), s(j)) * d(i, j));
		}
	}
	
	return z;
}

void CRAFT(int N, struct point * P, double * F, int * S)
{
	int i, j, k, count = 1;
	double Cmin, C;
	int Imin, Jmin;
	int tt, f;
	int *T;

	T = (int *)malloc(sizeof(int)*N);
	Cmin = zf(N, P, F, S);

	while (1)
	{
		printf("\n\n第%d次迭代:", count++);
		printf("\n====================================================");
		printf("\n            搬運費用:%10.3f 布置方案:", Cmin);

		for (k = 0; k < N; k++)
		{
			printf("t%-2d", s(k)+1);
		}
		f = 0;

		for (i = 0; i < N - 1; i++)
		{
			for (j = i+1; j < N; j++)
			{
				for (k = 0; k < N; k++)
				{
					t(k) = s(k);
				}
				tt = t(i);
				t(i) = t(j);
				t(j) = tt;
				C = zf(N, P, F, T);
				printf("\n互換(%2d,%2d),搬運費用:%10.3f 布置方案:", i+1, j+1, C);
				for (k = 0; k < N; k++)
				{
					printf("t%-2d", t(k)+1);
				}	

				if (Cmin > C)
				{
					Cmin = C;
					Imin = i;
					Jmin = j;
					f = 1;
				}
			}
		}

		if (f == 1)
		{
			tt = s(Imin);
			s(Imin) = s(Jmin);
			s(Jmin) = tt;
		}
		else
		{
			printf("\n\n最佳布置方案:");
			for (i = 0; i < N; i++)
			{
				printf("t%-2d", s(i)+1);
			}
			break;
		}
	}
}