2013年1月22日

UVa 216 - Getting in Line


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

int n, x[10], y[10], parent[10], end;
double d[10][10], min;

void dfs(int now, int depth, int* chk, int* prev, double dis) {
  int i;
  if (depth == n) {
    if (dis < min) {
      for (i = 1; i <= n; i++)
        parent[i] = prev[i];
      end = now;
      min = dis;
    }
    return;
  }
  for (i = 1; i <= n; i++)
    if (!chk[i]) {
      prev[i] = now;
      chk[i] = 1;
      dfs(i, depth + 1, chk, prev, dis + d[now][i]);
      prev[i] = i;
      chk[i] = 0;
    }
}

void path(int p) {
  if (parent[p] != p) path(parent[p]);
  else return;
  printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n", x[parent[p]], y[parent[p]], x[p], y[p], d[p][parent[p]]);
}

int main() {
  int T = 1;
  while (scanf("%d", &n) && n) {
    int i, j;
    for (i = 1; i <= n; i++)
      scanf("%d%d", &x[i], &y[i]);
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        d[i][j] = 16 + sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
    int check[10] = {}, prev[10];
    for (i = 1; i <= n; i++)
      prev[i] = parent[i] = i;
    min = 2e9;
    for (i = 1; i <= n; i++) {
      check[i] = 1;
      dfs(i, 1, check, prev, 0);
      check[i] = 0;
    }
    puts("**********************************************************");
    printf("Network #%d\n", T++);
    path(end);
    printf("Number of feet of cable required is %.2lf.\n", min);
  }
  return 0;
}

沒有留言:

張貼留言