poj 1040 Transportation

Transportation

Description

Ruratania is just entering capitalism and is establishing new enterprising activities in many fields in- cluding transport. The transportation company TransRuratania is starting a new express train from city A to city B with several stops in the stations on the way. The stations are successively numbered, city A station has number 0, city B station number m. The company runs an experiment in order to improve passenger transportation capacity and thus to increase its earnings. The train has a maximum capacity n passengers. The price of the train ticket is equal to the number of stops (stations) between the starting station and the destination station (including the destination station). Before the train starts its route from the city A, ticket orders are collected from all onroute stations. The ticket order from the station S means all reservations of tickets from S to a fixed destination station. In case the company cannot accept all orders because of the passenger capacity limitations, its rejection policy is that it either completely accept or completely reject single orders from single stations.

Write a program which for the given list of orders from single stations on the way from A to B determines the biggest possible total earning of the TransRuratania company. The earning from one accepted order is the product of the number of passengers included in the order and the price of their train tickets. The total earning is the sum of the earnings from all accepted orders.

Input

The input file is divided into blocks. The first line in each block contains three integers: passenger capacity n of the train, the number of the city B station and the number of ticket orders from all stations. The next lines contain the ticket orders. Each ticket order consists of three integers: starting station, destination station, number of passengers. In one block there can be maximum 22 orders. The number of the city B station will be at most 7. The block where all three numbers in the first line are equal to zero denotes the end of the input file.

Output

The output file consists of lines corresponding to the blocks of the input file except the terminating block. Each such line contains the biggest possible total earning.

Sample Input

10 3 4
0 2 1
1 3 5
1 2 7
2 3 10
10 5 4
3 5 10
2 4 9
0 2 5
2 5 8
0 0 0

Sample Output

19
34

运输

描述

Ruratania 刚刚进入资本主义，并正在包括交通在内的许多领域开展新的企业活动。运输公司 TransRuratania 正在启动从城市 A 到城市 B 的新快车，途中在车站停靠了几站。车站依次编号，A市车站编号为0，B市车站编号为m。该公司进行了一项试验，以提高客运能力，从而增加其收益。火车最多可容纳 n 名乘客。火车票的价格等于始发站和目的站（包括目的站）之间的站（站）数。在列车从 A 市出发前，从所有沿线车站收集车票订单。S站的订票是指所有从S到固定目的站的订票。如果公司因载客量限制不能接受所有订单，其拒绝政策是完全接受或完全拒绝来自单个站点的单个订单。

编写一个程序，根据从 A 到 B 途中单站的给定订单列表，确定 TransRuratania 公司可能的最大总收入。一个已接受订单的收入是订单中包含的乘客人数与其火车票价格的乘积。总收入是所有已接受订单的收入总和。

输入

输入文件被分成块。每个区块的第一行包含三个整数：列车的载客量n、城市B站的数量和所有车站的订票数量。下一行包含票证订单。每张票单由三个整数组成：起点站、终点站、乘客人数。在一个区块中最多可以有 22 个订单。城市B站的编号最多为7。第一行三个数字都为零的块表示输入文件的结尾。

输出

输出文件由与输入文件中除终止块之外的块相对应的行组成。每条这样的行都包含可能的最大总收入。

样本输入

10 3 4
0 2 1
1 3 5
1 2 7
2 3 10
10 5 4
3 5 10
2 4 9
0 2 5
2 5 8
0 0 0

样本输出

19
34

代码：

#include 
#include 
int orders[27][4];
int maxPeoples, endStation, numOrders;;
int max;
int leane[8];
void train(int n, int sum)
{
     int i; 
     if (sum > max)
        max = sum;
     if(n >= numOrders)
          return;
     for (i = orders[n][0]; i < orders[n][1]; i++)
         if (leane[i]+orders[n][2] > maxPeoples)
            break;
     if (i >= orders[n][1]) {
        for (i = orders[n][0]; i < orders[n][1]; i++)
            leane[i] += orders[n][2];
        train(n+1, sum+orders[n][3]);
        for (i = orders[n][0]; i < orders[n][1]; i++)
            leane[i] -= orders[n][2];
     }
     train(n+1, sum);
}
int main()
{
    int i;
    int a, b, p; 
    while (scanf("%d%d%d", &maxPeoples, &endStation, &numOrders), maxPeoples||endStation||numOrders) {
          memset(leane, 0, sizeof(leane));
          for (i = 0; i < numOrders; i++) {
              scanf("%d%d%d", &a, &b, &p);
              orders[i][0] = a;
              orders[i][1] = b;
              orders[i][2] = p;
              orders[i][3] = (b-a)*p;
          }
          max = 0;
          train(0, 0);
          printf("%d\n", max);
    }
    return 0;
}