UVa-11389 : The Bus Driver Problem

問題概要

配列Xと配列Y(長さはともにN(<100))が与えられる。X[i]+Y[j]がdを越えたらr*(X[i]+Y[j]-d)のコストが発生する。最小重み二部マッチングを求める問題。

acceptされたコード

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

const int MAX_N = 100;
const int MAX_V = 2*MAX_N + 2;
const int INF = 1<<29;

int N, D, R;
int as[MAX_N], bs[MAX_N];

typedef pair<int, int> P;
struct edge{ int to, cap, cost, rev; };
int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];

void add_edge(int from, int to, int cap, int cost){
	G[from].push_back((edge){to,cap,cost,G[to].size()});
	G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}

int min_cost_flow(int s, int t, int f){
	int res = 0;
	fill(h, h+V, 0);
	while(f > 0){
		priority_queue<P, vector<P>, greater<P> > que;
		fill(dist, dist+V, INF);
		dist[s] = 0;
		que.push(P(0,s));
		while(!que.empty()){
			P p = que.top(); que.pop();
			int v = p.second;
			if(dist[v] < p.first) continue;
			for(int i=0; i<G[v].size(); i++){
				edge &e = G[v][i];
				if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(P(dist[e.to],e.to));
				}
			}
		}
		if(dist[t] == INF){
			return -1;
		}
		for(int v = 0; v<V; v++) h[v] += dist[v];

		int d = f;
		for(int v=t; v != s; v = prevv[v]){
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d*h[t];
		for(int v=t; v!=s; v=prevv[v]){
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return res;
}

void init(){
	for(int i=0; i<N; i++){
		scanf("%d", as+i);
	}
	for(int i=0; i<N; i++){
		scanf("%d", bs+i);
	}

	for(int i=0; i<MAX_V; i++){
		G[i].clear();
	}
}

int solve(){
	const int source = 2*N, sink = source + 1;
	V = sink + 1;

	for(int i=0; i<N; i++){
		add_edge(source, i, 1, 0);
	}
	for(int j=0; j<N; j++){
		add_edge(j+N, sink, 1, 0);
	}

	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			int cost = max(0, as[i] + bs[j] - D);
			add_edge(i, j+N, 1, cost);
		}
	}

	return R*min_cost_flow(source, sink, N);
}

int main(){
	while(scanf("%d%d%d",&N,&D,&R),N){
		init();
		printf("%d\n", solve());
	}
	return 0;
}