图的匹配.doc

6.1 二分图的概念 设G=(V,E)是一个无向图，如果顶点V可分割两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。如下图是一个二分图图1 上图可以存储为邻接矩阵： (0 0 0 1 1 1 0 也可以存储为（1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0） 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 )5. 2 最大匹配1.最大匹配的概念设G=(V,E)是一个图,如果M是边E的子集,且M中的任意两条边都不与同一个顶点相关联,则称M是G的一个匹配。G的边数最多的匹配称为G的最大匹配。2最大匹配算法最大流方法1) 将图变成单向有向图A-B2) 添加源点s和汇点t将图变为 s-A-B-t, 如上图一可变为 图23）设每条有向边的容量c为14）源点到汇点的最大流即为最大匹配 例一：混双配对问题：乒乓球队中有N名男运动员和M名女运动员。由于某种原因，在混双比赛中，某些男运动员和某些女运动员不能配对比赛，这使得教练很苦恼，他希望你能帮他找出一种最优得配对方案，组成今尽可能最多得混双配对。输入文件：第一行两个正整数N，M（NM=100),表示男、女运动的个数。以下是一个NM的矩阵。若Aij1表示第i名男运动员可与第j名女运动员配对；若Aij0则表示不能配对。输出文件：只有一个整数，为最多的混双配对。程序如下：program tpp1;const inf=input.txt; maxn=100;typearc=record c, f:integer;end;node=record last:integer; checked:boolean;end;varmap:array1.maxn+2,1.maxn+2 of arc;imp:array1.maxn+2 of node;n,m,s,t:integer;fp:text;procedure init;var i,j:integer;beginassign(fp,inf);reset(fp);readln(fp,n,m);fillchar(map,sizeof(map),0);for i:=1 to n do for j:=1 to m do read(fp,mapi,n+j.c);s:=n+m+1;t:=n+m+2;for i:=1 to n do maps,i.c:=1;for i:=1 to m do mapi+n,t.c:=1;close(fp);end;procedure main;var flow,i:integer;function find:boolean; var i,j:integer; begin find:=false; fillchar(imp,sizeof(imp),0); imps.last:=s; repeat i:=1; while (in+m+2 then exit; for j:=1 to n+m+2 do if impj.last=0 then begin if mapi,j.f0 then impj.last:=-i; end; impi.checked:=true; until impt.last0; find:=true; end;procedure updata;var i,j:integer;begin i:=t;j:=abs(impi.last); repeat if impi.last0 then inc(mapj,i.f) else dec(mapi,j.f); i:=j;j:=abs(impi.last); until i=s;end;begin while find do updata; flow:=0; for i:=1 to n do inc(flow,maps,i.f); writeln(maxpp=,flow);end;begininit;main;end.5.匹配的最大（小）效应值先看一个问题最优工作问题(work)CCS集团有n台机器。为了生产需要，新招募了n名技术人员。他们有丰富的专业技术，每个人都熟悉各种机器的操作。现在每个人只能操作一台机器，而每个人对不同机器的控制能力又有差别，技术员i对机器j的控制能力称为ability(i，j)。要求给每人分配一台机器，使得所有人控制能力之和最大。 输入格式： 第一行仅有一个整数n(n=100)，第二行开始是一个n*n的矩阵，第i行第j列表示ability(i，j)(ability(i，j)0 then for j:=1 to 2*n+2 do if (ai,j.fbestj.value then begin bestj.value:=besti.value+ai,j.w; bestj.fa:=i; quit:=false; end;until quit;if bestt.value1 then find:=true else find:=false;end;procedure add;var i,j:integer;begini:=t;while is do begin j:=besti.fa; inc(aj,i.f); ai,j.f:=-aj,i.f; i:=j end; inc(maxwork,bestt.value-1);end;begininit;while find do add;writeln(maxwork);end.最小费用最大流方法：program work;const maxn=100;type node1=record w,f,c:integer end;type node2=record value:integer; fa:integer;end;var a:array1.maxn+2,1.maxn+2 of node1; best:array1.maxn+2 of node2; n,maxwork,s,t:integer;procedure init;var i,j,x:integer;beginreadln(n);fillchar(a,sizeof(a),0);for i:=1 to n do for j:=n+1 to 2*n do begin read(x); ai,j.c:=1; ai,j.w:=-x; aj,i.w:=x; end;s:=2*n+1;t:=2*n+2;for i:=1 to n do begin as,i.c:=1; an+i,t.c:=1; end;maxwork:=0;end;function find:boolean;var i,j:integer;quit:boolean;beginfor i:=1 to 2*n+2 do besti.value:=maxint;bests.value:=0;repeatquit:=true; for i:=1 to 2*n+2 do if besti.valuemaxint then for j:=1 to 2*n+2 do if (ai,j.fai,j.c) then if besti.value+ai,j.wbestj.value then begin bestj.value:=besti.value+ai,j.w; bestj.fa:=i; quit:=false; end;until quit;if bestt.valuemaxint then find:=true else find:=false;end;procedure add;var i,j:integer;begini:=t;while is do begin j:=besti.fa; inc(aj,i.f); ai,j.f:=-aj,i.f; i:=j end; inc(maxwork,bestt.value);end;begininit;while find do add;writeln(-maxwork);end.练习：1.丘比特之剑:在东方男女相爱是千里姻缘一线牵,两人无论身处何处都能相爱,但在西方丘比特之剑射程有限,只有射程内的男女两人才能相爱,求最大缘分和。输入文件：第一行是一个正整数k，表示丘比特的射程。第二行为正整数n（n30),第三到n+2行是男人的姓名和位置坐标,第n+3到第2n+2行是女人的姓名和位置坐标:格式是 name x y。剩下的部分是男人和女人间的缘分值 p格式为name1 name2 p，以End作为文件的结束标志，其中姓名字符串的长度不超过20，p=255,每两人之间的缘分值只描述一次,没描述的缘分值为1。输出文件:只有一个数,最大的缘分和的值。2.最少皇后控制在国际象棋中，皇后能向八个方向攻击(如图4-5所示，图中黑点格子为皇后的位置，标有K的格子为皇后可攻击到的格子)。现在给定一个M*N(N、M均不大于10)的棋盘，棋盘上某些格子有障碍。每个皇后被放置在无障碍的格子中，且它就控制了这个格子，除此，它可以从它能攻击到的最多8个格子中选一个格子来控制，如图4-5(b)所示，标号为1的格子被一个皇后所控制。 请你编一程序，计算出至少有多少个皇后才能完全控制整个棋盘。 输入格式： 输入文件的第一行有两个整数M和N，表示棋盘的行数与列数。接下来M行N列为一个字符矩阵，用号表示空白的格子，x表示有障碍的