給$n$個事件，每個事件發生在$t$時間點，座標$(x, y)$，
對於每個事件，可以多派遣一個人去解決，或者讓已經去解決某個事件的人走過來(如果從事件$i$走到事件$j$，必須滿足$t_i>t_j$且$|t_i-t_j|\ge |x_i-x_j|+|y_i-y_j|$)。
問最少需要派遣幾個人才能完成所有事件。
$1\le n\le 1000, 0\le x,y\le 1000, 0\le t< 1440$
這題好棒!!
完全沒想到可以這樣做。
首先考慮建有向圖，如果可以從事件$i$走到事件$j$，就建一條$i\to j$的邊，這樣問題就變成在有向圖上找最少路徑覆蓋整張圖。
然而這樣還不可做QQ，我們再把有向圖的入度出度拆成兩個點，每條$i\to j$的邊改成$i_{out}\to j_{in}$，可以發現這張圖會是二分圖(入度出度不會連邊)。
而在圖上每多一條匹配，象徵意義就是完成事件$i$的人接著去做事件$j$，換句話說，就是可以少派遣一個人!
所以答案會是n-匹配數，其中二分圖最大匹配我們使用匈牙利演算法。
複雜度$\mathcal{O}(VE)$。(理論上$E$是可以到$V^2$的，而$V=N\le 1000$，但是還是能過，匈牙利真神奇)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
signed main() { EmiliaMyWife
int t;
cin >> t;
while(t--) {
int n, ans;
cin >> n;
ans = n;
vector<int> t(n), x(n), y(n);
for(int i = 0; i < n; i++)
cin >> t[i] >> x[i] >> y[i];
vector<int> ais(n, -1), bis(n, -1);
vector<vector<int>> edge(n);
vector<bool> vis(n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(t[i] < t[j] && abs(x[i] - x[j]) + abs(y[i] - y[j]) <= t[j] - t[i]) {
edge[i].push_back(j);
if(!~ais[i] && !~bis[j])
ais[bis[j] = i] = j, ans--;
}
function<bool(int)> dfs = [&] (int u) {
vis[u] = true;
for(int v : edge[u])
if(!~bis[v] || (!vis[bis[v]] && dfs(bis[v])))
return ais[bis[v] = u] = v, true;
return false;
};
for(int i = 0; i < n; i++)
if(!~ais[i] && (fill(vis.begin(), vis.end(), false), dfs(i)))
ans--;
cout << ans << '\n';
}
}
|