QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#218050 | #6546. Greedy Bipartite Matching | zhoukangyang | TL | 3ms | 13508kb | C++11 | 2.3kb | 2023-10-17 17:48:24 | 2023-10-17 17:48:24 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long
using namespace std;
const int N = 2e5 + 7, inf = 1e9;
int n, m, q;
ll ans;
vi e[N];
int matl[N], matr[N], disl[N], disr[N];
bool bfs() {
L(i, 1, n)
disl[i] = inf, disr[i] = inf;
queue < int > q;
L(i, 1, n)
if(!matl[i])
disl[i] = 0, q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto&v : e[u])
if(disr[v] > disl[u] + 1) {
disr[v] = disl[u] + 1;
if(matr[v])
disl[matr[v]] = disr[v], q.push(matr[v]);
}
}
L(i, 1, n)
if(!matr[i] && disr[i] < inf)
return true;
return false;
}
int visr[N], visl[N];
int dfs(int x, int mnd) {
if(disl[x] >= mnd)
return false;
if(visl[x])
return false;
visl[x] = true;
for(auto&v : e[x]) {
// cout << x << " -> " << v << ' ' << disr[v] << ' ' << visr[v] << endl;
if(disr[v] == disl[x] + 1 && !visr[v]) {
// cout << x << " -> " << v << ' ' << matr[v] << endl;
visr[v] = true;
if(!matr[v] || dfs(matr[v], mnd)) {
matr[v] = x,
matl[x] = v;
return true;
}
}
}
return false;
}
int stk[N], top;
int main () {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> q;
int ans = 0;
while(q--) {
int m;
cin >> m;
while(m--) {
int x, y;
cin >> x >> y;
e[x].emplace_back(y);
}
while(bfs()) {
L(i, 1, n) visl[i] = false, visr[i] = false;
int mn = inf;
L(i, 1, n) if(!matr[i]) mn = min(mn, disr[i]);
int win = 0;
L(x, 1, n)
if(!matl[x] && disl[x] == 0 && dfs(x, mn)) {
++ans;
win = 1;
break;
}
if(!win) {
assert(false);
}
// cout << endl;
// L(i, 1, n) {
// cout << matl[i] << ' ' << matr[i] << endl;
// }
}
L(u, 1, n) if(disl[u] == inf) {
top = 0;
L(p, 0, sz(e[u]) - 1) {
int v = e[u][p];
if(disr[v] < inf) {
stk[++top] = p;
}
}
R(i, top, 1) {
e[u].erase(e[u].begin() + stk[i]);
}
}
cout << ans << ' ';
}
return 0;
}
/*
3 2
1
1 1
2
2 1
1 2
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 13508kb
input:
3 4 2 1 1 1 2 2 1 1 2 2 2 1 3 3 2 1 3 3
output:
1 2 2 3
result:
ok 4 number(s): "1 2 2 3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 8512kb
input:
0 0
output:
result:
ok 0 number(s): ""
Test #3:
score: 0
Accepted
time: 0ms
memory: 13216kb
input:
2 2 0 2 1 2 1 2
output:
0 1
result:
ok 2 number(s): "0 1"
Test #4:
score: -100
Time Limit Exceeded
input:
100000 1 200000 78475 45796 32145 46393 92550 13904 73461 34145 96461 92851 56319 77067 77530 84437 76343 51543 77507 99269 76411 89382 1779 61393 43608 96136 84269 74828 14858 35967 32085 94909 19877 175 1482 94391 12424 55020 64369 92588 81296 7903 25433 46033 36294 61129 73556 84837 8419 10215 12...