Posted on 四月 19th, 2008.
又是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: […]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 6th, 2008.
第一次完成了KM的题目~撒花~
不过还是参考了好多次标程,后面要加强KM的熟练程度~
一定不能再出小毛病…比如把search := false;写做search := true;之类的…
题目第一行输入一个n,表示二分图左右结点分别有n个.
第二行n个数,第i个数xi表示左边第i个结点向右边结点连边时权值为xi^2.
后面n行,第i+2第一个数ki表示左边第i个结点向右边连边的条数,接下来ki个数表示向哪些结点连边.
很裸的KM,随便写写就可以.
附代码.
{
Beloved Sons; SGU 210
- sqybi’s code
- 最大匹配
- KM Kuhn-Munkres
}
//for my winsty
program sgu210_sqybi;
const
fin = ’sgu210.in’;
fout = ’sgu210.out’;
nn = 400;
var
i, j, m, n, x: longint;
b: array[1..nn, 1..nn]of longint;
vx, vy: array[1..nn]of boolean;
a, lx, ly: array[1..nn]of longint;
match: array[1..nn]of longint;
function search(x: longint): boolean;
[…]
Read Full Post |
Make a Comment ( 4 so far )