UVA301 Transportation

GRAPH, DFS

출처: UVA UVA301 Transportation

SOL)
각각의 주어진 주문량은 선택을 할지 안할지 2가지 경우로 나뉘며
이를 모든 경우에 대해서 살펴본다.
주문량이 최대 22개 이므로 수행가능.


[-] Collapse

#include<iostream>
#include<stdio.h>
using namespace std;

int from[22], to[22], people[22];
int mx, cap[8], sum, orders;

void DFS(int now);

int main(){
    freopen("input.txt", "r", stdin);
    int capacity, station;

    while (cin >> capacity >> station >> orders){
        if (capacity == 0 && station == 0 && orders == 0) break;

        mx = 0;
        for (int i = 0; i < orders; i++)
            cin >> from[i] >> to[i] >> people[i];

        for (int i = 0; i <= station; i++) cap[i] = capacity;
        sum = 0;
        DFS(0);
        cout << mx << endl;
    }
    return 0;
}
void DFS(int now){
    bool flag;

    if (now == orders){//최대 값 갱신
        if (sum > mx) mx = sum;
    }
    else{
        flag = false;

        for (int i = from[now]; i < to[now]; i++){
            if (cap[i] < people[now]) flag = true; //선택을 못한다면
        }

        if (!flag){//선택을 할수 있다면
            for (int i = from[now]; i < to[now]; i++) cap[i] -= people[now];
            //선택
            sum += people[now] * (to[now] - from[now]);
            DFS(now + 1);
            //복원 //선택을 안하겠다는 의미
            for (int i = from[now]; i < to[now]; i++) cap[i] += people[now];
            sum -= people[now] * (to[now] - from[now]);
        }
        DFS(now + 1);
    }
}