TOI 1116 — 运送物资
又是KM的题目.对任意一对仓库和物资之间以距离的相反数为权值建边,然后KM.注意权值为负是因为需要求带权最小匹配.写的依然不熟,很诧异自己当时写了一次KM就一直没动过…忘得死死的.还好还有时间,最近复习好KM和HopCroft.似乎Dinic没法代替HopCroft…
{ TOI 1116; 运送物资 - sqybi’s code - 带权最小匹配 - KM}program toi1116_sqybi; const fin = ’snow.in’; fout = ’snow.out’; nn = 100;
var n, m, nx, ny, i, j, r: longint; ch: char; x, y: array[1..nn, 0..1]of longint; d: array[1..nn, 1..nn]of longint; match, lx, ly: array[1..nn]of longint; vx, vy: array[1..nn]of boolean;
function search(x: […]