QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#454558#6546. Greedy Bipartite MatchingpandapythonerTL 0ms3852kbC++207.8kb2024-06-25 03:52:222024-06-25 03:52:23

Judging History

你现在查看的是最新测评结果

  • [2024-06-25 03:52:23]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3852kb
  • [2024-06-25 03:52:22]
  • 提交

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...

output:


result: