rt，大概就是 $i < j$ 有边则令 $G_{i,\,j} = x_{i,\,j},\,G_{j,\,i} = -x_{i,\,j}$。其中 $x_{i,\,j},\,i < j$ 是随机值。然后求这个矩阵的秩，秩除以二是最大匹配。

然后不知道咋构造。