ACM-ICPC World Finals 2016 B解法

B: Branch Assignment

問題

n 頂点 r 辺の重み付き有向グラフがある。頂点はv_1 ... v_nとする。
そのうち、v_1 ... v_bのb個の頂点はbranch (支店）が置いてあり、v_{b+1}にはheadquarter(本店)がある。
支店をs個のグループに分割したい(s <= b)。
月に一度、各支店は同じグループに属する、自分以外の支店にメッセージをおくる。
メッセージの送信は同じグループ内の全ての組合せに対して独立に行われ、送信者から本店に最短コストで送り、本店から受信者に最短コストで送る。
全体のコスト総和を最小にするようなグループ分割を求め、その最小コストを出力せよ。
グループは少なくとも1つの支店がある必要がある。

制約

2 <= n <= 5000
1 <= r <= 50000
b <= n-1
1 <= s <= b

本店から支店、支店から本店へのパスは必ず存在する。

解法

2つのパートに分ける。

1 (最短経路)

本店から各支店へのコストは本店をスタートとしてDijkstra法で求める。
各支店から本店へのコストは、全ての辺を逆向きに張ったグラフにおいて、本店をスタートとしてDijkstra法で求める。
以降、支店jから本店へのコストをup_jとし、本店から支店jへのコストをdn_jとする。

2 (グループ分割)

ある1つのグループ S_i に掛かるコストを求める。
up_jについて、支店jから送信するとき、グループの他のメンバーの数 |S_i|-1 倍掛かる。
dn_jについて、支店jが受信するとき、|S_i|-1 倍掛かる。
つまりグループS_iのコストは
https://chart.googleapis.com/chart?cht=tx&chs=30&chl=%28%7CS_i%7C-1%29%5Csum_%7Bj%5Cin%20S_i%7D%28up_j%2Bdn_j%29

ここで重要なのはup_j, dn_jの係数はそのグループのサイズにのみ依存することである。
よって、(up_j + dn_j)が小さい支店ほど、大きいグループに入れるのが最適である。
支店は(up_j + dn_j)が大きい順にソートされているとすると次の動的計画法が考えられる。

dp[i][j] := 支店を大きい方からj個使って、i個のグループ作った時の最小コスト
c(a, b) := 支店aからbをグループにした時のグループのコスト

for i in 0..S-1:
    for j in 0..N-1:
        for k in 1..N:
            dp[i+1][j+k] = min(dp[i+1][j+k], dp[i][j] + c(j+1, j+k))

これではO(S N^2)でTLE。kはグループのサイズに相当するが、枝刈りとしてグループのサイズはだんだん小さくなることがわかるので「残りのグループ全てk以上にできるか?」を入れて修正する。

for i in 0..S-1:
    for j in 0..N-1:
        for k in 1..N: if j + k * (S-i) <= N:
            dp[i+1][j+k] = min(dp[i+1][j+k], dp[i][j] + c(j+1, j+k))

実はこのj, kのループは合計で N log Nになるため、全体でO(S N log N)でめでたしめでたし。

コード

#include<queue>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

// O(E log V)
typedef LL Cost;
struct Edge {
    int src, dst;
    Cost cst;
    bool operator<(const Edge &y) const {
	return cst > y.cst; // reversed
    }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
LL INF;

struct Dijkstra {
    vector<Cost> len;
    vector<int> prev;
    Dijkstra(const Graph &G, int s=0) {
	int N = G.size();
	len.assign(N, INF);
	len[s] = Cost();
	prev.resize(N, -1);
	priority_queue<Edge> Q;
	Q.push((Edge){ -1, s, Cost() });
	while (!Q.empty()) {
	    Edge e = Q.top(); Q.pop();
	    if (len[e.dst] < e.cst) continue;
	    for (int i=0; i<(int)G[e.dst].size(); i++) {
		Edge f = G[e.dst][i];
		if (len[f.dst] > f.cst + e.cst) {
		    len[f.dst] = f.cst = f.cst + e.cst;
		    prev[f.dst] = e.dst;
		    Q.push(f);
		}
	    }
	}
    }
    vector<int> pathTo(int goal) { // [s, ..., g]
	vector<int> v;
	for (int x=goal; x!=-1; x=prev[x]) v.push_back(x);
	reverse(v.begin(), v.end());
	return v;
    }
};
	
int N, B, S, M;
Graph G, R;
LL dp[5011][5011];

int main() {
    memset(&INF, 0x3f, sizeof INF);
    scanf("%d%d%d%d", &N, &B, &S, &M);
    G = R = Graph(N);
    REP (i, M) {
	int x, y, d;
	scanf("%d%d%d", &x, &y, &d);
	x--; y--;
	G[x].push_back((Edge){x, y, d});
	R[y].push_back((Edge){y, x, d});
    }

    vector<Cost> up = Dijkstra(R, B).len;
    vector<Cost> dn = Dijkstra(G, B).len;

    vector<LL> x(B), sums(B+1);
    REP (i, B) {
	x[i] = up[i] + dn[i];
    }
    sort(x.rbegin(), x.rend());
    REP (i, B) {
	sums[i+1] = x[i] + sums[i];
    }

    memset(dp, 0x3f, sizeof dp);

    dp[0][0] = 0;
    REP (i, S) {
	REP (j, B) if (dp[i][j] != INF) {
	    for (int l=1; j + l * (S-i) <= B; l++) {
		amin(dp[i+1][j+l], dp[i][j] + (sums[j+l] - sums[j]) * (l - 1));
	    }
	}
    }

    printf("%lld\n", dp[S][B]);

    return 0;
}