QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#454558 | #6546. Greedy Bipartite Matching | pandapythoner | TL | 0ms | 3852kb | C++20 | 7.8kb | 2024-06-25 03:52:22 | 2024-06-25 03:52:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
const ll inf = 1e18;
mt19937 rnd(234);
struct num {
vector<pair<int, int>> a;
num() {}
num(int x, int y) {
a = { make_pair(x, y) };
}
bool is_zero() {
return a.empty();
}
bool is_nonnegative() {
if (a.empty()) {
return true;
}
return a[0].second > 0;
}
bool is_negative() {
return !is_nonnegative();
}
};
num operator+(const num& a, const num& b) {
num c;
c.a.reserve((int)a.a.size() + (int)b.a.size());
int i = 0, j = 0;
while (i < (int)a.a.size() and j < (int)b.a.size()) {
if (a.a[i].first < b.a[j].first) {
c.a.push_back(a.a[i]);
i += 1;
} else if (a.a[i].first > b.a[j].first) {
c.a.push_back(b.a[j]);
j += 1;
} else if (a.a[i].second + b.a[j].second != 0) {
c.a.push_back(make_pair(a.a[i].first, a.a[i].second + b.a[j].second));
i += 1;
j += 1;
} else {
i += 1;
j += 1;
}
}
while (i < (int)a.a.size()) {
c.a.push_back(a.a[i]);
i += 1;
}
while (j < (int)b.a.size()) {
c.a.push_back(b.a[j]);
j += 1;
}
return c;
}
num operator-(const num& a, const num& b) {
num c;
c.a.reserve((int)a.a.size() + (int)b.a.size());
int i = 0, j = 0;
while (i < (int)a.a.size() and j < (int)b.a.size()) {
if (a.a[i].first < b.a[j].first) {
c.a.push_back(a.a[i]);
i += 1;
} else if (a.a[i].first > b.a[j].first) {
c.a.push_back(make_pair(b.a[j].first, -b.a[j].second));
j += 1;
} else if (a.a[i].second - b.a[j].second != 0) {
c.a.push_back(make_pair(a.a[i].first, a.a[i].second - b.a[j].second));
i += 1;
j += 1;
} else {
i += 1;
j += 1;
}
}
while (i < (int)a.a.size()) {
c.a.push_back(a.a[i]);
i += 1;
}
while (j < (int)b.a.size()) {
c.a.push_back(b.a[j]);
j += 1;
}
return c;
}
bool operator<(const num& a, const num& b) {
int i = 0, j = 0;
while (i < (int)a.a.size() and j < (int)b.a.size()) {
if (a.a[i].first < b.a[j].first) {
return (a.a[i].second < 0);
} else if (a.a[i] > b.a[j]) {
return (b.a[j].second > 0);
} else if (a.a[i].second - b.a[j].second != 0) {
return a.a[i].second < b.a[j].second;
}
i += 1;
j += 1;
}
if (i < (int)a.a.size()) {
return a.a[i].second < 0;
}
if (j < (int)b.a.size()) {
return b.a[i].second > 0;
}
return false;
}
struct edge {
int to;
num w;
int f, c;
int rvi;
edge() {}
edge(int to, const num& w, int c, int rvi) : to(to), w(w), f(0), c(c), rvi(rvi) {}
int rest() const {
return c - f;
}
};
namespace flow {
int n;
int q;
vector<vector<edge>> g;
void build(int _n, int _q) {
n = _n;
q = _q;
g.assign(n, vector<edge>());
}
void add_edge(int v, int to, int x = -1) {
int i = (int)g[v].size();
int j = (int)g[to].size();
if (x == -1) {
g[v].push_back(edge(to, num(), 1, j));
g[to].push_back(edge(v, num(), 0, i));
} else {
g[v].push_back(edge(to, num(x, -1), 1, j));
g[to].push_back(edge(v, num(x, 1), 0, i));
}
}
vector<num> dist;
vector<int> usd;
void dijkstra(int s) {
dist.assign(n, num(-1, 1));
dist[s] = num();
usd.assign(n, false);
usd[s] = true;
set<pair<num, int>> q;
q.insert(make_pair(dist[s], s));
while (!q.empty()) {
int v = q.begin()->second;
usd[v] = true;
q.erase(q.begin());
for (auto& e : g[v]) {
int to = e.to;
if (usd[to] or e.rest() <= 0) {
continue;
}
if (dist[v] + e.w < dist[to]) {
if (dist[to].a.empty() or dist[to].a[0].first != -1) {
q.erase(make_pair(dist[to], to));
}
dist[to] = dist[v] + e.w;
q.insert(make_pair(dist[to], to));
}
}
}
}
vector<int> pntr;
vector<int> dist_bfs;
void bfs(int s){
dist_bfs.assign(n, n + 10);
dist_bfs[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto &e: g[v]){
int to = e.to;
if(e.rest() <= 0 or !e.w.is_zero()){
continue;
}
if(dist_bfs[to] > dist_bfs[v] + 1){
dist_bfs[to] = dist_bfs[v] + 1;
q.push(to);
}
}
}
}
bool dfs(int v, int t) {
if (v == t) {
return true;
}
usd[v] = true;
for (int& i = pntr[v]; i < (int)g[v].size(); i += 1) {
auto& e = g[v][i];
int to = e.to;
if (usd[to] or e.rest() <= 0 or !e.w.is_zero() or dist_bfs[to] != dist_bfs[v] + 1) {
continue;
}
if (dfs(to, t)) {
e.f += 1;
g[to][e.rvi].f -= 1;
usd[v] = false;
return true;
}
}
return false;
}
vector<int> flow(int s, int t) {
vector<int> result(q);
num delta = num();
while (1) {
dijkstra(s);
if (!usd[t]) {
break;
}
delta = delta + dist[t];
if (delta.is_nonnegative()) {
break;
}
assert((int)delta.a.size() == 1);
rep(v, n) {
if (!usd[v]) {
continue;
}
for (auto& e : g[v]) {
int to = e.to;
if (!usd[to]) {
continue;
}
e.w = e.w + dist[v] - dist[to];
}
}
bfs(s);
pntr.assign(n, 0);
usd.assign(n, false);
while (1) {
bool ok = dfs(s, t);
if (!ok) {
break;
}
result[delta.a[0].first] += -delta.a[0].second;
}
}
for (int i = 1; i < q; i += 1) {
result[i] += result[i - 1];
}
return result;
}
};
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, q;
cin >> n >> q;
flow::build(2 * n + 2, q);
rep(i, n) {
flow::add_edge(2 * n, i);
flow::add_edge(n + i, 2 * n + 1);
}
rep(i, q) {
int t;
cin >> t;
rep(j, t) {
int u, v;
cin >> u >> v;
--u;
--v;
flow::add_edge(u, n + v, i);
}
}
auto result = flow::flow(2 * n, 2 * n + 1);
assert((int)result.size() == q);
rep(i, q) {
cout << result[i] << " ";
}
cout << "\n";
return 0;
}
/*
3 4
2
1 1
1 2
2
1 1
2 2
2
1 3
3 2
1
3 3
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3852kb
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: 0ms
memory: 3640kb
input:
0 0
output:
result:
ok 0 number(s): ""
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
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...