匹配的最大（小）效应值

匹配的最大（小）效应值

先看一个问题

最优工作问题(work)
CCS集团有n台机器。为了生产需要，新招募了n名技术人员。他们有丰富的专业技术，每个人都熟悉各种机器的操作。现在每个人只能操作一台机器，而每个人对不同机器的控制能力又有差别，技术员i对机器j的控制能力称为ability(i，j)。要求给每人分配一台机器，使得所有人控制能力之和最大。
    输入格式：
    第一行仅有一个整数n(n<=100)，第二行开始是一个n*n的矩阵，第i行第j列表示ability(i，j)(ability(i，j)<=300)。
    输出格式：
    仅一行：包含一个整数S，表示最大控制能力和。
样例：
INPUT．TXT
3

3 5 2
3 2 8
7 5 8
OUTPUT．TXT
20

对于本问题，可以建立如图3所示的图，x1，x2，x3分别代表3个技术员，y1，y2，y3分别表示3台机器，有向边(xi，yj)表示xi控制机器yj，边上的权表示技术员对该机器的控制能力。显然图3是一个二分图。现在要求每个技术员唯一控制一台机器，且要控制能力之和最大。这样问题就转化为一个关于二分图求最佳匹配的问题

         

图3                                                                                                        

算法分析 下面用流的算法，求最佳匹配和最大控制能力和。
    (1)在二分图基础上，构造一个网络N(如图4)。
    ①增加一个源点s与一个汇点t；
    ②从s向原图中顶点xi引一条弧；从顶点yi向t引一条弧；
    ③令所有的弧的容量都为1；
    ④令弧(s，xi)和(yi，t)上的费用为O。

    (2)对网络N求最大费用最大流(只要将所有权改为负，就是最小费用最大流)。
    这样构造网络的正确性道理很显然。首先因为网络中每个弧流量都为1，所以就能保证每个技术员控制一台机器，一台机器也唯一由一个技术员控制，最大流量必为n，其次要求最大费用最大流，即可保证所有技术员的控制机器的能力之和最大。
    在编程时，可以边读人数据边产生网络N，接着运用一次求最大费用最大流算法，最后，在最大流的方案中通过找所有流为1的边(vi，vj)，就可得到各个技术员控制机器的情况及最大控制能力之和。

程序如下：

最大费用最大流方法：

program work;
const maxn=100;
type node1=record
  w,f,c:integer
  end;
type node2=record
  value:integer;
  fa:integer;
end;
var a:array[1..maxn+2,1..maxn+2] of node1;
  best:array[1..maxn+2] of node2;
  n,maxwork,s,t:integer;
procedure init;
var i,j:integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
for i:=1 to n do
  for j:=n+1 to 2*n do
   begin
   read(a[i,j].w);
   a[i,j].c:=1;
   a[j,i].w:=-a[i,j].w;
   end;
s:=2*n+1;
t:=2*n+2;
for i:=1 to n do
  begin
   a[s,i].c:=1;
   a[n+i,t].c:=1;
  end;
maxwork:=0;
end;
function find:boolean;
var i,j:integer;
quit:boolean;
begin
fillchar(best,sizeof(best),0);
best.value:=1;
repeat
  quit:=true;
  for i:=1 to 2*n+2 do
     if best.value>0 then
    for j:=1 to 2*n+2 do
     if (a[i,j].f<a[i,j].c) then
      if best.value+a[i,j].w>best[j].value then
         begin
        best[j].value:=best.value+a[i,j].w;
         best[j].fa:=i;
         quit:=false;
         end;
until quit;
if best[t].value>1 then find:=true else find:=false;
end;
procedure add;
var i,j:integer;
begin
i:=t;
while i<>s do
  begin
   j:=best.fa;
   inc(a[j,i].f);
   a[i,j].f:=-a[j,i].f;
   i:=j
  end;
  inc(maxwork,best[t].value-1);
end;
begin
init;
while find do add;
writeln(maxwork);
end.