OJ Board

Code: Select all

//PROBLEM NO	: 10724
//PROBLEM NAME	: Road Construction
//DATE			: 06 / 09 / 05

#include <stdio.h>
#include <string.h>
#include <math.h>

#define min(a,b) a<b ? a : b

const int max = 55;

const double eps = 1e-10;
const double inf = 1e15;

double init[max][max];
double prev[max][max];
double curr[max][max];

struct point
{
	double x;
	double y;
} pnt[max];

int nNode;
int nEdge;


double euler(int i, int j)
{
	double x = pnt[i].x - pnt[j].x, y = pnt[i].y - pnt[j].y;
	return sqrt(x*x + y*y);
}

/*
int equals(double a, double b)
{
	if(fabs(a-b) < eps)
		return 1;
	return 0;
}
*/

int main(void)
{
	int i, j;
	int frm, mid, to;

	double newCost, prevCost, edgeCost;
	double prevSum, currSum;
	double diff;

	double minSum, minEdge;
	int u, v;
	
#ifndef ONLINE_JUDGE
	freopen("c:/programs/input/10724.txt", "r", stdin);
#endif

	while(scanf("%d %d", &nNode, &nEdge) == 2)
	{
		if(nNode==0 && nEdge == 0)
			break;

		memset(init, 0, sizeof(init));

		for(i=1; i<=nNode; i++)
			scanf("%lf %lf", &pnt[i].x, &pnt[i].y);

		for(i=0; i<nEdge; i++)
		{
			scanf("%d %d", &frm, &to);

			init[frm][to] = init[to][frm] = euler(frm, to);
		}

		memcpy(prev, init, sizeof(prev));

		for(mid=1; mid<=nNode; mid++)
		{
			for(frm=1; frm<=nNode; frm++)
			{
				for(to=frm+1; to<=nNode; to++)
				{
					if(prev[frm][mid] && prev[mid][to] && frm != to)
					{
						prevCost = prev[frm][to];
						newCost = prev[frm][mid] + prev[mid][to];
						
						if(!prevCost || prevCost > newCost)
							prev[frm][to] = newCost;
					}
				}
			}
		}

		
		prevSum = 0.0;
		for(frm=1; frm<=nNode; frm++)
		{
			for(to=frm+1; to<frm; to++)
			{
				prev[frm][to] = prev[to][frm];
				prevSum += prev[frm][to];
			}
		}
		
		minSum = inf;
		for(frm=1; frm<=nNode; frm++)
		{
			for(to=frm+1; to<=nNode; to++)
			{
				if(!init[frm][to])
				{
					edgeCost = euler(frm, to);
					currSum = prevSum;

					for(i=1; i<=nNode; i++)
					{
						for(j=i+1; j<=nNode; j++)
						{
							//newCost = min((prev[i][frm] + edgeCost + prev[to][j]), (prev[i][to] + edgeCost + prev[frm][j]));
							newCost = prev[i][frm] + edgeCost + prev[to][j];
							
							if(newCost < prev[i][j])
							{
								diff = prev[i][j] - newCost;
								currSum -= diff;
							}
						}
					}

					if(currSum < minSum)
					{
						minSum = currSum;
						minEdge = edgeCost;

						u = frm;
						v = to;
					}

					//if(equals(currSum, minSum) && edgeCost < minEdge)

					if(currSum == minSum && edgeCost < minEdge)
					{
						minEdge = edgeCost;

						u = frm;
						v = to;
					}
				}
			}
		}

		minSum += (1.0 + eps);


		//if(equals(minSum, prevSum) || minSum > prevSum)
		if(minSum >= prevSum)
			printf("No road required\n");
		else
			printf("%d %d\n", u, v);			
	}
	
	return 0;
}

Code: Select all

#include<iostream>
#include<math.h>
#define INF 21474478.0
using namespace std;

double  links[53][53],checking[53][53],traveling[53][53],solution[1225][3];
int points[53][2];
int no_points,no_links;

void Initialize()
{
	for(int i=1;i<=no_points;i++)
		for(int j=1;j<=no_points;j++)
	{
		if(i==j)
		{
			links[i][j] = 0;
			checking[i][j]=0;
		}
		else
		{
			links[i][j] = INF;
			checking[i][j]=-1;
		}
	}
}


double calculate_distance(int m,int n)
{
	int a = points[m][0] - points[n][0];
	int b = points[m][1] - points[n][1];
	return sqrt((a*a) + (b*b));
}

void ReInitialize_traveling()
{
	for(int i=1;i<=no_points;i++)
		for(int j=1;j<=no_points;j++)
			traveling[i][j] = links[i][j];
}

void floydwarshall(int n)
{
	for (int k=1;k<=n;k++) /* k -> is the intermediate point */
		for (int i=1;i<=n;i++) /* start from i */
			for (int j=1;j<=n;j++) /* reaching j */
				if (links[i][k] + links[k][j] < links[i][j])
	{
		links[i][j] = links[i][k]+links[k][j];
		links[j][i] = links[i][k]+links[k][j];
	}
}

double cost_calculation(int n)
{
	double cost = 0.0;
	for(int i=1;i<=no_points;i++)
		for(int j=i+1;j<=no_points;j++)
	{
		if(n==2)
			cost += traveling[i][j];
		else
			cost += links[i][j];
	}
	return cost;
}

void show_array(int n)
{
	for(int i=1;i<=no_points;i++)
	{
		for(int j=1;j<=no_points;j++)
		{
			if(n==1)
				cout<<" "<<links[i][j];
			else
				cout<<" "<<traveling[i][j];
		}
		cout<<endl;
	}
}

double minimum(double a,double b,double c)
{
	if(a<=b && a<=c)
		return a;
	if(b<=a && b<=c)
		return b;
	else
		return c;
}

int main()
{
	double dist;
	int m,n;
	while(scanf("%d %d\n",&no_points,&no_links) && (no_points || no_links))
	{
		Initialize();
		for(int i=0;i<no_points;i++)
			scanf("%d %d",&points[i+1][0],&points[i+1][1]);
		for(int i=0;i<no_links;i++)
		{
			scanf("%d %d",&m,&n);
			dist = calculate_distance(m,n);
			links[m][n] = dist;
			links[n][m] = dist;
			checking[m][n] = 0;
			checking[n][m] = 0;
		}

		floydwarshall(no_points);//on links matrices
		double preCost = cost_calculation(1);

		int index = 0,ansX,ansY;
		for(int u=1;u<=no_points;u++)
		{
			for(int v=u+1;v<=no_points;v++)
			{
				if(checking[u][v]==-1)
				{
					solution[index][0] = u;
					solution[index][1] = v;
					ReInitialize_traveling();
					dist = calculate_distance(u,v);
					for(int i=1;i<=no_points;i++)
						for(int j=1;j<=no_points;j++)
						traveling[i][j] = minimum(traveling[i][j],traveling[i][u]+dist+traveling[v][j],traveling[i][v]+dist+traveling[u][j]);
					solution[index][2] = preCost  - cost_calculation(2);

					if(solution[index][2] > 1.0)
						index++;
				}
			}
		}
		if(index>0)
		{
			int a,b;
			double newmin,min = 0,dist_X_Y,newdist;
			for(int i=0;i<index;i++)
			{
				a = solution[i][0];
				b = solution[i][1];
				newdist = calculate_distance(a,b);
				newmin = solution[i][2];
				if(min<newmin)
				{
					min = newmin;
					ansX = a;
					ansY = b;
					dist_X_Y = newdist;
				}
				else if(min==newmin && newdist<dist_X_Y)
				{
					dist_X_Y=newdist;
					ansX = a;
					ansY = b;

				}
				else if(min==newmin && newdist==dist_X_Y && a<ansX)
				{
					ansX = a;
					ansY = b;
				}
				else if(min==newmin && newdist==dist_X_Y && a==ansX && b<ansY)
				{
					ansY = b;
				}
			}
			cout<<ansX<<" "<<ansY<<endl;
		}
		else
			cout<<"No road required\n";
	}
}

Code: Select all

10 20
23 62 15 28 72 83 56 80 30 30 98 82 51 76 39 21 65 83 72 9 
1 2 1 3 2 4 2 5 4 6 4 7 6 8 3 9 7 10 
7 5
4 9
1 2
10 2
9 8
6 9
6 5
9 7
1 4
8 2
8 6

10 20
41 40 10 85 9 57 37 43 17 92 55 32 47 21 69 44 87 23 8 78 
1 2 2 3 3 4 1 5 3 6 5 7 4 8 3 9 4 10 
8 1
6 4
8 9
2 4
8 3
9 3
4 5
2 10
4 9
3 7
3 1

10 20
44 68 75 59 12 41 78 56 18 52 72 64 61 1 27 3 74 48 66 40 
1 2 2 3 2 4 2 5 3 6 3 7 7 8 3 9 6 10 
4 9
8 5
5 6
2 9
4 3
7 9
5 1
4 1
7 6
7 6
9 3

20 50
9 65 81 99 96 64 40 77 0 79 81 72 49 91 29 42 2 86 23 96 33 34 53 97 43 17 73 5 86 62 39 97 44 99 76 39 34 16 94 0 
1 2 2 3 1 4 1 5 2 6 4 7 7 8 6 9 7 10 7 11 2 12 9 13 8 14 13 15 6 16 4 17 7 18 4 19 9 20 
13 6
12 7
4 2
13 11
10 1
10 16
14 13
2 12
10 20
2 18
16 19
19 17
5 20
6 17
9 10
13 20
9 19
1 6
18 9
16 5
15 16
7 6
12 11
3 15
7 8
20 19
11 1
16 11
12 13
3 19
19 13
0 0

Code: Select all

5 8
4 7
2 6
8 11