用C＋＋编写一个km算法，寻找最优匹配，输入顶点数和边权值，输出匹配结果和最大边权和。同时边权值为零的两顶点不能匹配

好的,我可以为您介绍如何使用C++编写KM算法来寻找最优匹配。以下是一个实现该功能的C++程序:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 310;
const int INF = 0x3f3f3f3f;

int n;
int w[MAXN][MAXN];
int lx[MAXN], ly[MAXN];
int match[MAXN];
bool visx[MAXN], visy[MAXN];
int slack[MAXN];

bool dfs(int x) {
    visx[x] = true;
    for (int y = 0; y < n; y++) {
        if (!visy[y] && lx[x] + ly[y] == w[x][y]) {
            visy[y] = true;
            if (match[y] == -1 || dfs(match[y])) {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

int km() {
    memset(match, -1, sizeof(match));
    memset(ly, 0, sizeof(ly));
    for (int i = 0; i < n; i++) {
        lx[i] = -INF;
        for (int j = 0; j < n; j++) {
            if (w[i][j] > lx[i]) {
                lx[i] = w[i][j];
            }
        }
    }

    for (int x = 0; x < n; x++) {
        memset(slack, 0x3f, sizeof(slack));
        while (true) {
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            if (dfs(x)) break;
            
            int d = INF;
            for (int i = 0; i < n; i++) {
                if (!visx[i] && slack[i] < d) {
                    d = slack[i];
                }
            }
            for (int i = 0; i < n; i++) {
                if (visx[i]) lx[i] -= d;
                if (visy[i]) ly[i] += d;
                else slack[i] -= d;
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        if (match[i] != -1) {
            res += w[match[i]][i];
        }
    }
    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> w[i][j];
            if (w[i][j] == 0) {
                w[i][j] = -INF;
            }
        }
    }

    int max_weight = km();
    cout << "匹配结果:" << endl;
    for (int i = 0; i < n; i++) {
        if (match[i] != -1) {
            cout << i << " -- " << match[i] << endl;
        }
    }
    cout << "最大边权和: " << max_weight << endl;

    return 0;
}

这个程序实现了KM算法来寻找最优匹配。主要步骤如下:

1. 读取输入的顶点数和边权值。
2. 将边权值为0的边权值设为负无穷,确保这些顶点不会被匹配。
3. 实现KM算法的核心函数km(),该函数使用匈牙利算法来寻找最大权匹配。
4. 在主函数中调用km()函数,并输出匹配结果和最大边权和。

使用这个程序,您可以输入顶点数和边权值,程序将输出最优匹配和最大边权和。