QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#369825#898. 二分图最大匹配IsrothyCompile Error//C++232.2kb2024-03-28 18:25:262024-03-28 18:25:26

Judging History

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

  • [2024-03-28 18:25:26]
  • 评测
  • [2024-03-28 18:25:26]
  • 提交

answer

#include <queue>
#include <vector>
struct BipartiteGraph {
    std::vector<std::vector<int>> adj;
    std::vector<int> dx, dy, s, t;
    int nl, nr;
    BipartiteGraph(int nl, int nr)
        : adj(nl), dx(nl), dy(nr), s(nl, -1), t(nr, -1), nl(nl), nr(nr) {}
    void add_edge(int u, int v) {
        adj[u].push_back(v);
    }
    bool bfs() {
        fill(dx.begin(), dx.end(), -1);
        fill(dy.begin(), dy.end(), -1);
        int ret = -1;
        std::queue<int> q;
        for (int u = 0; u < nl; ++u) {
            if (s[u] == -1) {
                dx[u] = 0;
                q.push(u);
            }
        }
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            if (ret != -1 && dx[u] > ret) {
                break;
            }
            for (auto v: adj[u]) {
                if (dy[v] == -1) {
                    dy[v] = dx[u];
                    if (t[v] != -1) {
                        dx[t[v]] = dy[v] + 1;
                        q.push(t[v]);
                    } else {
                        ret = dx[u];
                    }
                }
            }
        }
        return ret != -1;
    }
    bool dfs(int u) {
        for (auto v: adj[u]) {
            if (dy[v] == dx[u]) {
                dy[v] = -1;
                if (t[v] == -1 || dfs(t[v])) {
                    s[u] = v;
                    t[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int maximum_matching() {
        int res = 0;
        while (bfs()) {
            for (int u = 0; u < nl; ++u) {
                if (s[u] == -1 && dfs(u)) {
                    ++res;
                }
            }
        }
        return res;
    }
};

int main() {
    int l, r, m;
    scanf("%d %d %d", &l, &r, &m);
    BipartiteGraph bg(l, r);
    for (int i = 0; i < m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        bg.add_edge(x, y);
    }
    printf("%d\n", bg.maximum_matching());
    for (int i = 0; i < l; ++i) {
        if (bg.s[i] != -1) {
            printf("%d %d\n", i, bg.s[i]);
        }
    }
    return 0;
}

详细

answer.code: In function ‘int main()’:
answer.code:71:5: error: ‘scanf’ was not declared in this scope
   71 |     scanf("%d %d %d", &l, &r, &m);
      |     ^~~~~
answer.code:78:5: error: ‘printf’ was not declared in this scope
   78 |     printf("%d\n", bg.maximum_matching());
      |     ^~~~~~
answer.code:2:1: note: ‘printf’ is defined in header ‘<cstdio>’; did you forget to ‘#include <cstdio>’?
    1 | #include <queue>
  +++ |+#include <cstdio>
    2 | #include <vector>