NOT A BLOG | sqybi

SGU 210 — Beloved Sons

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;
    var
      i, t: longint;
    begin
      search := false;
      if vx[x] then exit;
      vx[x] := true;
      search := true;
      for i:=1 to n do
        if not vy[i] and (lx[x] + ly[i] = b[x, i]) then begin
          vy[i] := true;
          t := match[i];
          match[i] := x;
          if (t = 0) or search(t) then exit;
          match[i] := t;
        end;
      search := false;
    end;

  procedure km;
    var
      i, j, k, delta: longint;
    begin
      fillchar(match, sizeof(match), 0);
      fillchar(lx, sizeof(lx), 0);
      fillchar(ly, sizeof(ly), 0);
      for i:=1 to n do
        for j:=1 to n do
          if b[i, j] > lx[i] then
            lx[i] := b[i, j];
      for i:=1 to n do
        repeat
          fillchar(vx, sizeof(vx), false);
          fillchar(vy, sizeof(vy), false);
          if search(i) then break;
          delta := maxlongint;
          for j:=1 to n do
            if vx[j] then
              for k:=1 to n do
                if not vy[k] then
                  if delta > lx[j] + ly[k] - b[j, k] then
                    delta := lx[j] + ly[k] - b[j, k];
          for j:=1 to n do
            if vx[j] then
              lx[j] := lx[j] - delta;
          for j:=1 to n do
            if vy[j] then
              ly[j] := ly[j] + delta;
        until false;
    end;

  begin
    assign(input, fin);
    assign(output, fout);
    reset(input);
    rewrite(output);

    readln(n);
    for i:=1 to n do read(a[i]);
    readln;
    for i:=1 to n do begin
      read(m);
      for j:=1 to m do begin
        read(x);
        b[x, i] := a[i] * a[i];
      end;
      readln;
    end;

    km;

    for i:=1 to n do
      write(ord(b[match[i], i]<>0)*match[i], ‘ ‘);

    close(input);
    close(output);
  end.

阅读(176 次)

Make a Comment

Make A Comment: ( 4 so far )

4 Responses to “SGU 210 — Beloved Sons”

Comments RSS Feed

Where's The Comment Form?