「HDU6094」Rikka with K-Match
题目链接题目大意$n \times m$ 的网格图 要求你求一个大小为 $k$ 的最小权匹配。$n \leq 40000,m \leq 4,k \leq \frac{nm}{2}$多组数据 数据组数 $T \leq 1000$，保证只有三组数据 $n > 100$。题解首先这个题是可以二分图染色跑费用流的。所以设 $w_i$ 表示 $i$ 条边的答案。很容易有 $w_i-w_{i-1}...
题目链接题目大意$n \times m$ 的网格图 要求你求一个大小为 $k$ 的最小权匹配。$n \leq 40000,m \leq 4,k \leq \frac{nm}{2}$多组数据 数据组数 $T \leq 1000$，保证只有三组数据 $n > 100$。题解首先这个题是可以二分图染色跑费用流的。所以设 $w_i$ 表示 $i$ 条边的答案。很容易有 $w_i-w_{i-1}...