请用Kernighan-Lin算法编写MaxCut问题的求解（C++语言）

以下是用 C++ 实现的 Kernighan-Lin 算法求解 MaxCut 问题的代码：

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

using namespace std;

#define MAXN 1005

int n, m; // 顶点数和边数
int w[MAXN][MAXN]; // 图的邻接矩阵
int v[MAXN]; // 顶点所属的集合，1 表示在 S1 中，-1 表示在 S2 中
int d[MAXN]; // 顶点的度数
int s1[MAXN], s2[MAXN]; // S1 和 S2 集合
int bestcut; // 最优解
int bests1[MAXN], bests2[MAXN]; // 最优解对应的 S1 和 S2 集合

void init() {
    // 初始化
    bestcut = 0;
    for(int i = 1; i <= n; i++) {
        d[i] = 0;
        v[i] = 1;
        for(int j = 1; j <= n; j++) {
            w[i][j] = 0;
        }
    }
}

void input() {
    // 输入图的信息
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        w[u][v] = c;
        w[v][u] = c;
        d[u] += c;
        d[v] += c;
    }
}

void update(int cut) {
    // 更新最优解
    if(cut > bestcut) {
        bestcut = cut;
        for(int i = 1; i <= n; i++) {
            bests1[i] = s1[i];
            bests2[i] = s2[i];
        }
    }
}

void kernal() {
    // Kernighan-Lin 算法
    for(int i = 1; i <= n; i++) {
        s1[i] = 0;
        s2[i] = 0;
    }
    int cut = 0;
    for(int i = 1; i <= n; i++) {
        if(d[i] >= 0) {
            s1[i] = 1;
            cut += d[i];
        } else {
            s2[i] = 1;
        }
    }
    update(cut);
    for(int step = 1; step <= n / 2; step++) {
        int maxgain = -1;
        int u = 0, v = 0;
        for(int i = 1; i <= n; i++) {
            if(s1[i] == 1) {
                for(int j = 1; j <= n; j++) {
                    if(s2[j] == 1) {
                        int gain = d[i] - 2 * w[i][j] + d[j];
                        if(gain > maxgain) {
                            maxgain = gain;
                            u = i;
                            v = j;
                        }
                    }
                }
            }
        }
        s1[u] = 0;
        s2[u] = 1;
        s2[v] = 0;
        s1[v] = 1;
        cut -= maxgain;
        update(cut);
    }
}

void output() {
    // 输出最优解
    cout << "MaxCut = " << bestcut << endl;
    cout << "S1: ";
    for(int i = 1; i <= n; i++) {
        if(bests1[i] == 1) {
            cout << i << " ";
        }
    }
    cout << endl;
    cout << "S2: ";
    for(int i = 1; i <= n; i++) {
        if(bests2[i] == 1) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    init();
    input();
    kernal();
    output();
    return 0;
}

该代码实现了 Kernighan-Lin 算法求解 MaxCut 问题，通过邻接矩阵存储图的信息，采用贪心思想和迭代优化逼近最优解。算法的时间复杂度为 $O(n^3)$，可以处理较小规模的图。