HDU 3718 Similarity：KM 算法解字符映射最大匹配

問題建模

給定標準答案串（長 n），每行一個測試串。要求建立字符一對一映射，使相同位置字符匹配數最大。
構造二分圖：左側 26 個大寫字母（答案串字符），右側 26 個大寫字母（測試串字符），邊權為對應位置相同的次數。求最大權完美匹配，即 KM 算法。

KM 核心實現（節選）

struct KM {
    static const int MAXN = 27;
    int n, m, g[MAXN][MAXN];
    int Lx[MAXN], Ly[MAXN], slack[MAXN];
    int matchX[MAXN], matchY[MAXN];
    bool S[MAXN], T[MAXN];

    void init(int n) { this->n = n; memset(g, 0, sizeof(g)); }
    void addEdge(int u, int v, int w) { g[u][v] += w; } // 累加權重

    bool dfs(int u) {
        S[u] = true;
        for (int v = 0; v < m; ++v) if (!T[v]) {
            int delta = Lx[u] + Ly[v] - g[u][v];
            if (!delta) {
                T[v] = true;
                if (matchY[v] == -1 || dfs(matchY[v])) {
                    matchY[v] = u; matchX[u] = v;
                    return true;
                }
            } else slack[v] = min(slack[v], delta);
        }
        return false;
    }
    // update() 與 solve() 同 HDU 3722，略
};

主流程

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, k, m; scanf("%d%d%d", &n, &k, &m);
        char stdAns[10005][2];
        for (int i = 0; i < n; ++i) scanf("%s", stdAns[i]);
        while (m--) {
            KM solver; solver.init(26);
            for (int i = 0; i < n; ++i) {
                char c[2]; scanf("%s", c);
                solver.addEdge(stdAns[i][0]-'A', c[0]-'A', 1);
            }
            double ans = solver.solve() * 1.0 / n;
            printf("%.4lf\n", ans);
        }
    }
    return 0;
}

複雜度

O(26³) 每查詢，極快。總時間受 I/O 限制。