uva301 수송법(C++)

트랜스 루라타냐라는 철도회사는 A도시에서 B도시까지 가는 기차를 운영 중이다.

기차는 A도시에서 B도시의 종점역까지 가는대 여러 군대의 정차역을 들른다.

종점역을 포함한 정차역의 최대 갯수는 7개이며, 정차역마다 승객들이 타고 내릴 수 있다.

기차는 예약제로 운영 되는데 예약은 단체, 개인을 합쳐서 총 22개의 예약만을 받을 수 있다.

승객 한명당 기차요금은 출발 역에서 도착역 까지 가는데 도착역을 포함한 정차하는 역의 수와 같다.

그리고 각각의 역은 종점역을 포함해서 m개의 역에서 정차한다 했을때, 출발역 부터 0,1 ,2 ..m 으로 이름을 붙힌다.

기차 예약에는 몇명의 승객이 어디서 타서 어디서 내리는지 써있으며, 승객 수 가 제한되어 있기 때문에 승객을 다 수용할 수 없을 때에는 단체, 개인의 예약을 통째로 취소해야 한다.

이때 물론 최대의 이윤이 남게끔 예약을 취소해야 한다.

***예를 들어,  총 0 부터 5까지 총 5개의 정차역을 들르는 기차에 총 10명의 손님이 탈 수 있는데 예약이 3부터 5까지 6명, 0부터 4까지 5명 들어 왔을 때는 최대의 이윤을 남기기 위해 3부터 5까지 6명 예약을 취소해야 한다.


기차당 예약이 다음과 같은 형식으로 입력된다고 하자

첫번째 줄에는 고객 수송 재한n, 종점을 포함한 정차역 개수, 총 예약 개수가 순서대로 입력되고 다음 줄부터 한줄에 예약이 하나씩 다음과 같은 순서로 입력된다.
출발역, 도착역, 승객수.
그리고 또 다른 기차의 예약이 있으면 위와 똑같이 아래에 계속 입력 해준다.
입력은 0이 연속으로 3번 입력되면 끝난다.
출력은 각각의 기차가 낼수 있는 수익을 한줄에 한개씩 출력하면 된다.



문제를 풀기전에 어떤 식으로 풀어야 할지 생각해보자.

DFS를 이용해 최대 수송 제한을 넘지 않는 모든 경우를 검색하면서 최대 수익값을 갱신해 주면 되겠다.

#include <iostream>
#include <windows.h>

using namespace std;

int nor, m, c, cos[7], passenger[22], from[22], to[22];
/*각각 예약수, 최대값, 카운트, 역간 수용능력, 승객수, 출발역, 도착역이다.*/
void dfs(int num){
   
    int i;
    bool flag=true;
   
    if(num == nor){
          
           if(m < c){
                         m = c;
           }
           return;
    }
    for(i=from[num];i<to[num];i++){
                                    if(cos[i]<passenger[num]){
                                                              flag = false;
                                    }
    }
    if(flag){
             c+=(to[num]-from[num])*passenger[num];
             for(i=from[num];i<to[num];i++){
                                             cos[i]-=passenger[num];
             }
             dfs(num+1);
            
             c-=(to[num]-from[num])*passenger[num];
             for(i=from[num];i<to[num];i++){
                                             cos[i]+=passenger[num];
             }
    }
   
    dfs(num+1);
}
   
int main(){
   
    int i, capacity, nos;
   
    while(cin>>capacity>>nos>>nor){
                                   if(capacity==0&&nos==0&&nor==0)break;
                                   m = 0;
                                   c =0;
                                   for(i=0;i<nor;i++){
                                                      cin>>from[i]>>to[i]>>passenger[i];
                                   }
                                  
                                   for(i=0;i<nos ;i++)cos[i]=capacity;
/*역간 구간 수는 nos와 같다. nos가 열차의 기점을 제외한 수이기 때문이다.
기점과 첫번째 정차역 사이를 0으로 하여 종점역까지 숫자를 붙혀준다.*/
                                  
                                   dfs(0);
                                  
                                   cout<<m<<endl;
                                  
    }
   
    system("PAUSE");
   
    return 0;
}
실행결과

10 3 4
0 2 1
1 3 5
1 2 7
2 3 10
19
10 5 4
3 5 10
2 4 9
0 2 5
2 5 8
34
0 0 0
Press any key to continue . . .