#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
const int M = 2010;
bool was[N + M];
int n, m, k, mt[N + M];
vector<int> g[N + M];
vector<pair<int, int>> e;
bool kuhn(int x) {
if(was[x]) return false;
was[x] = true;
for(int j : g[x]) {
if(mt[j] == -1 || kuhn(mt[j])) {
mt[j] = x;
return true;
}
}
return false;
}
int max_matching(int l, int r) {
for(int i = 1; i <= n + m; i++) {
was[i] = false;
mt[i] = -1;
g[i].clear();
}
for(auto x : e) {
if(x.first >= l && x.first <= r) {
g[x.second].push_back(x.first + m);
g[x.first + m].push_back(x.second);
}
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= m; j++) was[j] = false;
kuhn(i);
}
int cnt = 0;
for(int i = 1; i <= n + m; i++) if(mt[i] != -1) cnt++;
return cnt;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
for(int i = 1; i <= k; i++) {
int u, v;
cin >> u >> v;
e.push_back({u, v});
}
int res = 0;
for(int i = 1; i <= n; i++) {
int l = 1, r = i, ans = -1;
while(l <= r) {
int mid = l + r >> 1;
if(max_matching(mid, i) == m) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if(ans == -1) continue;
res += ans;
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |