python/TangDou/AcWing/ErFenTu/POJ3216.md

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