用匈牙利法则写结构体

以下是一个使用匈牙利算法求二分图最大匹配的结构体示例代码：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;

struct BipartiteGraph {
    int n, m;
    int match[MAXN]; // 存储匹配情况
    bool vis[MAXN];
    bool g[MAXN][MAXN]; // 二分图的邻接矩阵

    bool dfs(int u) {
        for (int v = 1; v <= m; v++) {
            if (g[u][v] && !vis[v]) {
                vis[v] = true;
                if (match[v] == -1 || dfs(match[v])) {
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

    int hungarian() {
        int ans = 0;
        memset(match, -1, sizeof(match));
        for (int u = 1; u <= n; u++) {
            memset(vis, false, sizeof(vis));
            if (dfs(u)) ans++;
        }
        return ans;
    }
};

int main() {
    BipartiteGraph graph;
    memset(graph.g, false, sizeof(graph.g));
    cin >> graph.n >> graph.m;
    for (int i = 1; i <= graph.n; i++) {
        int u, v;
        cin >> u >> v;
        graph.g[u][v] = true;
    }
    cout << graph.hungarian() << endl;
    return 0;
}

在这个结构体中，我们将二分图的信息都放在了结构体内部。在 `main` 函数中，我们首先定义了一个 `BipartiteGraph` 类型的变量 `graph`，并将二分图的大小信息读入。然后，我们可以通过 `graph.g` 访问二分图的邻接矩阵，通过 `graph.match` 访问匹配情况，通过 `graph.hungarian()` 调用匈牙利算法求最大匹配。

这样做的好处是，将二分图的信息和算法的实现封装在了一起，让代码更加简洁和易读。同时也便于复用和维护。