weight.cpp

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

#include <fstream.h>
#include <string.h>

ifstream fin("weight.in");
ofstream fout("weight.out");
#define cout fout

const int MAX = 30+5;

int n;
int m[MAX][MAX], used[MAX];

main() {
   for (; fin >> n;) {
      if (n == 0) break;
      int i, j, k;
      for (i = 1; i <= n; i++) {
         m[i][i] = 0;
         for (j = i + 1; j <= n; j++) {
            fin >> m[i][j];
            m[j][i] = m[i][j];
         }
      }
      
      memset(used, 0, sizeof(used));
      
      int count;
      for (count = n; count > 2; count--) {
         int ok = 0, x, y, d;
         
         for (i = 1; !ok && i <= n; i++) if (!used[i])
            for (j = i + 1; !ok && j <= n; j++) if (!used[j]) {
               int now = 2147483647;
               for (k = 1; k <= n; k++) if (k != i && k != j && !used[k])
                  if (now == 2147483647) now = m[i][k] - m[j][k];
                  else if (now != m[i][k] - m[j][k]) break;
                  
               if (k > n) {
                  ok = 1;
                  x = i, y = j, d = now;
               }
            }
         
         used[y] = 1;
         for (i = 1; i <= n; i++) if (i != x && !used[i])
            m[x][i] = m[i][x] = m[x][i] + (m[x][y] - d) / 2;
      }
      
      for (i = 1; i <= n; i++)
         if (!used[i])
            break;
      for (j = i + 1; j <= n; j++)
         if (!used[j])
            break;
            
      cout << m[i][j] << endl;
   }
   
   return 0;   
}