\(POJ3216\) \(Repairing\) \(Company\)
一、题目描述
有\(n\)个维修站，给出了一个邻接矩阵(对称阵)表示每个维修站到其他维修站的花费的时间，\(-1\)表示不可达，然后给出了\(m\)个任务，给出了每个任务要在哪个维修站进行，起始时间 和 任务花费时间，问至少要几个维修人员才能准时进行任务。
二、题目分析
很明显的最小路径覆盖问题，刚开始脑子抽了，没求最短路直接就做了，题目只给了两点间直接到达的时间，还可以间接到达，用\(floyd\)求出最短路。。。
\(Code\)
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <vector>
#include <stack>
#include <cstdio>
using namespace std;
const int N = 25;
const int M = 205;
const int INF = 0x3f3f3f3f;
struct Task {
int id; // 维修站
int cost; // 花费时间
int st; // 起始时间
} task[M];
int m, n, g[N][N];
// 匈牙利算法
int match[M], st[M];
bool dfs(int u) {
for (int i = 0; i < m; i++) {
if (st[i]) continue;
// 这里很妙，不是真的把图建出来，而是直接利用原来的邻接矩阵，通过条件判断来决策，减少了代码!
if (task[u].st + task[u].cost + g[task[u].id][task[i].id] > task[i].st) continue;
st[i] = 1;
if (match[i] == -1 || dfs(match[i])) {
match[i] = u;
return 1;
}
}
return 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("POJ3216.in", "r", stdin);
#endif
while (~scanf("%d%d", &n, &m) && n + m) {
// 题目中给出的不可达值为-1，因为要求最短路，所以设置为INF
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
scanf("%d", &g[i][j]);
if (g[i][j] == -1) g[i][j] = INF;
}
// Floyd求任意两点间最短距离
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
// m个任务
for (int i = 0; i < m; i++)
scanf("%d%d%d", &task[i].id, &task[i].st, &task[i].cost);
// Hungary
memset(match, -1, sizeof match);
int res = 0;
for (int i = 0; i < m; i++) { // 枚举所个任务
memset(st, 0, sizeof st);
if (dfs(i)) res++;
}
// 输出结果
printf("%d\n", m - res);
}
return 0;
}