boosterc.cc

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

/*
Jiangsu Olympiad in Informatics
Training Problem
Testdata Creator Program

Task:            Signal Booster
Author:          Wenyuan Dai
Algorithm:       Greedy Method
Complex:         O(n)
Code:            Wenyuan Dai
Date:            3-27-2002
Time Limit:      2 second(Pentium IV 1.5G & 128MB RAM)
*/
#include <fstream.h>
#include <stdlib.h>
#include <time.h>

ofstream fin("booster.in");

class node {
  public:
    int link, length;
    node* next;
};

const int MAX = 100000+10;

int d[MAX] = {0}, max = 0;
node* g[MAX] = {0};

main() {
  srand(time(0));
  
  cout << "Enter the number of nodes:";
  int n;
  cin >> n;

  fin << n << endl;
  for (int i = 2; i <= n; i++) {
    int ID = rand()%(i - 1) + 1, length = rand()%10000 + 1;
    if (length > max) max = length;
    node* op = new node;
    op->link = ID, op->length = length, op->next = g[i], g[i] = op;
    op = new node;
    op->link = i, op->length = length, op->next = g[ID], g[ID] = op;
    d[i]++, d[ID]++;
  }

  for (int i = 1; i <= n; i++) {
    fin << d[i];
    for (node* op = g[i]; op; op = op->next)
      fin << ' ' << op->link << ' ' << op->length;
    fin << endl;
  }

  fin << rand()%max * 10 << endl;

  return 0;
}