图论-匈牙利算法模板

upd: 单向连边 \(a \rightarrow b\) ,显然应该在每一轮搜索中标记 \(b\) 集合的点。我误标记了 \(a\) ,这样就没有任何 \(a\) 类节点可以更改匹配了,完蛋。

    bool hungary(int p, int id)
    {
        for (int i = Fs[p]; i; i = Nx[i]) {
            int t = Vs[i];
            if (Mk[t] == id)
                continue;
            Mk[t] = id;
            if (!Lnk[t] || hungary(Lnk[t], id)) {
                Lnk[t] = p;
                return 1;
            }
        }
        return 0;
    }

    int main()
    {
        ans = 0;
        for (i = 1; i <= n; ++i)
            ans += hungary(i);
        printf("%d\n", ans);
        return 0;
    }
上一篇:vivado中未分配引脚的时序处理方法(转)


下一篇:DDR接口时序实例