백준 1585번: 경찰 (C++)

https://www.acmicpc.net/problem/1585

1585번: 경찰

---

Solved By: MCMF

 

네트워크 모델링에 있어서 다음 경우들을 생각하면 됩니다.

1) 출발 시간과 도착 시간이 매칭이 안 되는 경우

>> 도착 시간이 출발 시간보다 빠르다면 이건 말이 되지 않는 경우입니다.

>> edge를 만들어줄 필요가 없습니다.

2) 벌금을 내지 않는 경우

>> edge를 만들어주고, 벌금은 내지 않으므로 cost값은 0입니다.

3) 벌금을 내는 경우

>> edge를 만들어주고, 문제에서 제시된 규칙에 따라 벌금을 측정하여 cost값으로 할당합니다.

 

최대 비용은 모든 cost값을 음수로 만드는 테크닉을 이용합니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#define MAX 103
#define SOURCE 101
#define SINK 102
#define INF 1e9
using namespace std;

int n;
int io[MAX];
vector<int> adj[MAX];
int c[MAX][MAX], f[MAX][MAX];
int cost[MAX][MAX];
int T, F;

int MCMF(int source, int sink){
    int result = 0, cnt = 0;
    while(1){
        int parent[MAX], dist[MAX];
        fill(parent, parent + MAX, -1);
        fill(dist, dist + MAX, INF);
        queue<int> q;
        bool isinQ[MAX];
        
        dist[source] = 0;
        q.push(source);
        isinQ[source] = true;
        
        while(!q.empty()){
            int now = q.front(); q.pop();
            isinQ[now] = false;
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                
                if(dist[now] + cost[now][next] < dist[next]
                && c[now][next] - f[now][next] > 0){
                    dist[next] = dist[now] + cost[now][next];
                    parent[next] = now;
                    
                    if(!isinQ[next]){
                        q.push(next);
                        isinQ[next] = true;
                    }
                }
            }
        }
        
        if(parent[sink] == -1) break;
        
        int temp = INF;
        
        for(int i = sink; i != source; i = parent[i]){
            temp = min(temp, c[parent[i]][i] - f[parent[i]][i]);
        }
        
        for(int i = sink; i != source; i = parent[i]){
            result += temp * cost[parent[i]][i];
            
            f[parent[i]][i] += temp;
            f[i][parent[i]] -= temp;
        }
        
        cnt++;
    }
    
    if(cnt < n) return -1;
    else return result;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> io[i];
        adj[SOURCE].push_back(i);
        adj[i].push_back(SOURCE);
        c[SOURCE][i] = 1;
    }
    
    for(int i = 51; i <= n + 50; i++){
        cin >> io[i];
        adj[i].push_back(SINK);
        adj[SINK].push_back(i);
        c[i][SINK] = 1;
    }
    
    cin >> T >> F;
    
    for(int i = 1; i <= n; i++){
        for(int j = 51; j <= n + 50; j++){
            if(io[j] > io[i]){
                // 도착 시간 > 출발 시간
                adj[i].push_back(j);
                adj[j].push_back(i);
                c[i][j] = 1;
            }
            if(io[j] - io[i] < T){
                // 벌금 책정 방법
                int S = io[j] - io[i];
                int temp = (T - S) * (T - S);
                temp = min(temp, F);
                
                cost[i][j] = temp;
                cost[j][i] = -temp;
            }
        }
    }
    
    int minAns = MCMF(SOURCE, SINK);
    cout << minAns << ' '; 
    if(minAns < 0) return 0;
    
    // 최대 비용
    
    //init
    for(int i = 0; i < MAX; i++){
        for(int j = 0; j < MAX; j++){
            f[i][j] = 0;
        }
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 51; j <= n + 50; j++){
            cost[i][j] = -cost[i][j];
            cost[j][i] = -cost[j][i];
        }
    }
    
    int maxAns = -MCMF(SOURCE, SINK);
    cout << maxAns;
    
    return 0;
}