booster.cc

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

/*
Jiangsu Olympiad in Informatics
Training Problem
Standard 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>

ifstream fin("booster.in");
ofstream fout("booster.out");

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

const int MAX = 100000+10;

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

void dispose(node* op) {
  if (op) {
    dispose(op->next);
    delete op;
  }
}

main() {
  int n, p;
  fin >> n;
  for (int i = 1; i <= n; i++) {
    fin >> d[i];
    for (int j = 0; j < d[i]; j++) {
      node* op = new node;
      fin >> op->link >> op->length;
      op->next = g[i], g[i] = op;
    }
    if (d[i] == 1) q[++q[0]] = i;
  }
  fin >> p;

  int total = 0;
  for (int i = 1; i <= q[0]; i++)
    if (q[i] != 1) {
      int max = 0;
      for (node* op = g[q[i]]; op; op = op->next)
        if (op->length > max)
          max = op->length;

      if (max >= p) {
        total = -1;
        break;
      }
      
      if (st[q[i]] + max >= p) {
        total++;
        st[q[i]] = 0;
      }

      for (node* op = g[q[i]]; op; op = op->next)
        if (op->link != 1 && d[op->link]-- > 0) {
          if (st[op->link] < st[q[i]] + op->length)
            st[op->link] = st[q[i]] + op->length;

          if (d[op->link] == 1)
            d[op->link] = -1, q[++q[0]] = op->link;
        }
    }

  if (total == -1)
    fout << "No solution." << endl;
  else
    fout << total << endl;

  for (int i = 1; i <= n; dispose(g[i++]));

  return 0;
}