[백준] 12766 - 지사 배정

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

12766번: 지사 배정

b개의 지사를 s개의 프로젝트로 나누었을 때, 메시지 전달 비용의 최솟값을 구하는 문제이다. 

 

교차로 i에서 j까지의 최단거리를 v[i][j]라고 하자. 지사 a가 k개의 지사가 참여하는 프로젝트에 소속되어 있을 때, 지사 a와 관련된 전달 비용은 (k-1) * (v[a][b+1] + v[b+1][a])이다.

즉, 해당 프로젝트에 소속된 다른 지사가 어디인지와는 관계가 없다.

 

때문에 총 비용의 합계가 최소가 되게 하기 위해서는 (v[a][b+1] + v[b+1][a]) 값이 작은 지사들을 큰 프로젝트에, 값이 큰 지사들을 작은 프로젝트에 투입해야 한다.

각 지사들을 (v[a][b+1] + v[b+1][a]) 순서로 정렬하고 프로젝트를 분리하는 경우 Divide and Conquer Optimization을 적용하여 문제를 해결할 수 있다.

 

<C++ 코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int n, b, s, r;
int d[5001], rd[5001];
vector<pair<int, int> > v[5001], rv[5001];
vector<int> value;
 
long long sum[5001];
long long dp[5001][5001];
int p[5001][5001];
 
void dijkstra(int st, int dist[], vector<pair<int, int> > e[]){
    for(int i=1; i<=n; i++)
        dist[i] = 2147483647;
    dist[st] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push({0, st});
    while(!pq.empty()){
        int td = -pq.top().first, p = pq.top().second;
        pq.pop();
        if(td > dist[p]) continue;
        for(int i=0; i<e[p].size(); i++){
            int nd = td + e[p][i].second, np = e[p][i].first;
            if(nd < dist[np]){
                dist[np] = nd;
                pq.push({-nd, np});
            }
        }
    }
    return;
}
 
long long cost(int i, int j){
    return (sum[j] - sum[i]) * (j - i - 1);
}
 
void dnqo(int t, int l, int r, int pl, int pr){
    if(l > r) return;
    int mid = (l + r) / 2;
    dp[t][mid] = p[t][mid] = -1;
 
    for(int k=pl; k<=min(mid-1, pr); k++){
        long long tmp = dp[t-1][k] + cost(k, mid);
        if(dp[t][mid] == -1 || dp[t][mid] > tmp){
            dp[t][mid] = tmp;
            p[t][mid] = k;
        }
    }
 
    dnqo(t, l, mid-1, pl, p[t][mid]);
    dnqo(t, mid+1, r, p[t][mid], pr);
    return;
}
 
int main(){
    scanf("%d %d %d %d", &n, &b, &s, &r);
    for(int i=0; i<r; i++){
        int start, end, l;
        scanf("%d %d %d", &start, &end, &l);
        v[start].push_back({end, l});
        rv[end].push_back({start, l});
    }
 
    dijkstra(b+1, d, v);
    dijkstra(b+1, rd, rv);
 
    for(int i=1; i<=b; i++){
        value.push_back(d[i] + rd[i]);
    }
    sort(value.begin(), value.end());
 
    for(int i=1; i<=b; i++){
        sum[i] = sum[i-1] + value[i-1];
    }
 
    for(int i=1; i<=b; i++){
        dp[1][i] = sum[i] * (i - 1);
        p[1][i] = 1;
    }
    for(int i=2; i<=s; i++){
        dnqo(i, i, b, 0, b);
    }
    printf("%lld", dp[s][b]);
 
    return 0;
}