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; }