TIOJ 2175：搶拉麵 2

TIOJ 2175：搶拉麵 2

題目大意：在 $n\times m ≤ 300$ 的平面上每個點有人或是拉麵店，每間拉麵店有好吃度 $d$，你可以給每個人設置不同的 $k$，代表其 $x$ 座標和 $y$ 座標的距離都要 $≤ k$，在此範圍內會挑選好吃度最大的拉麵店去吃，問最多可以有多少拉麵店受到光顧。

解法：對每個人可以枚舉在不同距離下要去哪間拉麵店，分別建一條邊，之後跑二分圖最大匹配，如果有連到邊代表此人是第一位顧客，可使答案增加 $1$，如果找不到邊連代表拉麵店都有人去過了。最大匹配數即為答案。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 305;

int n, m, ans;
vector<pair<int, int>> person;
vector<tuple<int, int, int>> store;
pair<int, int> like[SIZE][SIZE];

vector<int> adj[SIZE];
int match[SIZE];
bool vs[SIZE];

bool bimatch (int pos) {
    for (int np : adj[pos]) {
        if (!vs[np]) {
            vs[np] = 1;
            if (match[np] == -1 || bimatch (match[np])) {
                match[np] = pos;
                return 1;
            }
        }
    }
    return 0;
}

void solve() {
    cin >> n >> m;
    FOR (i, 1, n) FOR (j, 1, m) {
        int x;
        cin >> x;
        if (x == 0) {
            person.pb (i, j);
        } else if (x > 0) {
            store.pb (i, j, x);
        }
    }
    n = person.size(), m = store.size();
    if (n == 0 || m == 0) {
        cout << "0\n";
        return;
    }
    FOR (i, 0, n - 1) {
        auto [x, y] = person[i];
        FOR (j, 0, m - 1) {
            auto [sx, sy, d] = store[j];
            like[i][max (abs (x - sx), abs (y - sy))] = max (like[i][max (abs (x - sx), abs (y - sy))], {d, j});
        }
        FOR (j, 1, 300) {
            like[i][j] = max (like[i][j], like[i][j - 1]);
            if (like[i][j] != like[i][j - 1]) {
                adj[i].pb (like[i][j].S);
            }
        }
    }
    fill (match, match + m, -1);
    FOR (i, 0, n - 1) {
        fill (vs, vs + m, 0);
        ans += bimatch (i);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！