AOJ-2251 : Merry Christmas

問題概要

頂点数N(<100)の重み付き無向グラフが与えられる。時刻t[i]に頂点v[i]にいるというクエリがL(<1000)個ある。全てのクエリを処理するのに最小何人いればよいか求める問題。

解法

クエリiの後にクエリjを処理できるかどうかで辺を張ってDAGを構成し最小パス被覆を求めればよい。

acceptされたコード

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

const int MAX_N = 100;
const int MAX_Q = 1000;
const int INF = (int)(1.05e9); 

int N, M, L;
int mat[MAX_N][MAX_N];
int ps[MAX_Q], ts[MAX_Q];

bool init() {
	scanf("%d%d%d", &N, &M, &L);
	for (int i = 0; i < N; ++i) {
		fill(mat[i], mat[i] + N, INF);
	}

	for (int _ = 0; _ < M; ++_) {
		int from, to, cost;
		scanf("%d%d%d", &from, &to, &cost);
		updateMin(mat[from][to], cost);
		updateMin(mat[to][from], cost);
	}

	for (int i = 0; i < L; ++i) {
		scanf("%d%d", ps + i, ts + i);
	}

	return N > 0;
}

int solve() {
	G.init(2*L);
	for (int k = 0; k < N; ++k) {
		mat[k][k] = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				updateMin(mat[i][j], mat[i][k] + mat[k][j]);
			}
		}
	}

	for (int i = 0; i < L; ++i) {
		for (int j = 0; j < L; ++j) if (i != j) {
			if (ts[i] + mat[ps[i]][ps[j]] <= ts[j]) {
				G.addUndirectedEdge(2*i, 2*j+1);
			}
		}
	}

	return L - calcBipartiteMatching(G);
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}
	return 0;
}