图匹配

图匹配作者：新军来源：－时间：2006-5-2610:57:22阅读次数：3846.1二分图的概念设G=(V,E)是一个无向图，如果顶点V可分割两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(iinA,jinB)，则称图G为一个二分图。如下图是一个二分图图1上图可以存储为邻接矩阵：(0001110也可以存储为（11100000101010100010101010）1010000110000010100000100000)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（N＋M=100),表示男、女运动的个数。以下是一个N×M的矩阵。若Aij＝1表示第i名男运动员可与第j名女运动员配对；若Aij＝0则表示不能配对。输出文件：只有一个整数，为最多的混双配对。程序如下：programtpp1;constinf='input.txt';maxn=100;typearc=recordc,f:integer;end;node=recordlast:integer;checked:boolean;end;varmap:array[1..maxn+2,1..maxn+2]ofarc;imp:array[1..maxn+2]ofnode;n,m,s,t:integer;fp:text;procedureinit;vari,j:integer;beginassign(fp,inf);reset(fp);readln(fp,n,m);fillchar(map,sizeof(map),0);fori:=1tondoforj:=1tomdoread(fp,map[i,n+j].c);s:=n+m+1;t:=n+m+2;fori:=1tondomap[s,i].c:=1;fori:=1tomdomap[i+n,t].c:=1;close(fp);end;proceduremain;varflow,i:integer;functionfind:boolean;vari,j:integer;beginfind:=false;fillchar(imp,sizeof(imp),0);imp[s].last:=s;repeati:=1;while(i=n+m+2)and((imp[i].last=0)orimp[i].checked)doinc(i);ifin+m+2thenexit;forj:=1ton+m+2doifimp[j].last=0thenbeginifmap[i,j].fifmap[j,i].f0thenimp[j].last:=-i;end;imp[i].checked:=true;untilimp[t].last0;find:=true;end;procedureupdata;vari,j:integer;begini:=t;j:=abs(imp[i].last);repeatifimp[i].last0theninc(map[j,i].f)elsedec(map[i,j].f);i:=j;j:=abs(imp[i].last);untili=s;end;beginwhilefinddoupdata;flow:=0;fori:=1tondoinc(flow,map[s,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)=300)。输出格式：仅一行：包含一个整数S，表示最大控制能力和。样例：INPUT．TXT3352328758OUTPUT．TXT20对于本问题，可以建立如图3所示的图，x1，x2，x3分别代表3个技术员，y1，y2，y3分别表示3台机器，有向边(xi，yj)表示xi控制机器yj，边上的权表示技术员对该机器的控制能力。显然图3是一个二分图。现在要求每个技术员唯一控制一台机器，且要控制能力之和最大。这样问题就转化为一个关于二分图求最佳匹配的问题图３算法分析下面用流的算法，求最佳匹配和最大控制能力和。(1)在二分图基础上，构造一个网络N(如图4)。①增加一个源点s与一个汇点t；②从s向原图中顶点xi引一条弧；从顶点yi向t引一条弧；③令所有的弧的容量都为1；④令弧(s，xi)和(yi，t)上的费用为O。(2)对网络N求最大费用最大流(只要将所有权改为负，就是最小费用最大流)。这样构造网络的正确性道理很显然。首先因为网络中每个弧流量都为1，所以就能保证每个技术员控制一台机器，一台机器也唯一由一个技术员控制，最大流量必为n，其次要求最大费用最大流，即可保证所有技术员的控制机器的能力之和最大。在编程时，可以边读人数据边产生网络N，接着运用一次求最大费用最大流算法，最后，在最大流的方案中通过找所有流为1的边(vi，vj)，就可得到各个技术员控制机器的情况及最大控制能力之和。程序如下：最大费用最大流方法：programwork;constmaxn=100;typenode1=recordw,f,c:integerend;typenode2=recordvalue:integer;fa:integer;end;vara:array[1..maxn+2,1..maxn+2]ofnode1;best:array[1..maxn+2]ofnode2;n,maxwork,s,t:integer;procedureinit;vari,j:integer;beginreadln(n);fillchar(a,sizeof(a),0);fori:=1tondoforj:=n+1to2*ndobeginread(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;fori:=1tondobegina[s,i].c:=1;a[n+i,t].c:=1;end;maxwork:=0;end;functionfind:boolean;vari,j:integer;quit:boolean;beginfillchar(best,sizeof(best),0);best[s].value:=1;repeatquit:=true;fori:=1to2*n+2doifbest[i].value0thenforj:=1to2*n+2doif(a[i,j].fifbest[i].value+a[i,j].wbest[j].valuethenbeginbest[j].value:=best[i].value+a[i,j].w;best[j].fa:=i;quit:=false;end;untilquit;ifbest[t].value1thenfind:=trueelsefind:=false;end;procedureadd;vari,j:integer;begini:=t;whileisdobeginj:=best[i].fa;inc(a[j,i].f);a[i,j].f:=-a[j,i].f;i:=jend;inc(maxwork,best[t].value-1);end;begininit;whilefinddoadd;writeln(maxwork);end.最小费用最大流方法：programwork;constmaxn=100;typenode1=recordw,f,c:integerend;typenode2=recordvalue:integer;fa:integer;end;vara:array[1..maxn+2,1..maxn+2]ofnode1;best:array[1..maxn+2]ofnode2;n,maxwork,s,t:integer;procedureinit;vari,j,x:integer;beginreadln(n);fillchar(a,sizeof(a),0);fori:=1tondoforj:=n+1to2*ndobeginread(x);a[i,j].c:=1;a[i,j].w:=-x;a[j,i].w:=x;end;s:=2*n+1;t:=2*n+2;fori:=1tondobegina[s,i].c:=1;a[n+i,t].c:=1;end;maxwork:=0;end;functionfind:boolean;vari,j:integer;quit:boolean;beginfori:=1to2*n+2dobest[i].value:=maxint;best[s].value:=0;repeatquit:=true;fori:=1to2*n+2doifbest[i].valuemaxintthenforj:=1to2*n+2doif(a[i,j].fifbest[i].value+a[i,j].wbeginbest[j].value:=best[i].value+a[i,j].w;best[j].fa:=i;quit:=false;end;untilquit;ifbest[t].valueend;procedureadd;vari,j:integer;begini:=t;whileisdobeginj:=best[i].fa;inc(a[j,i].f);a[i,j].f:=-a[j,i].f;i:=jend;inc(maxwork,best[t].value);end;begininit;whilefinddoadd;writeln(-maxwork);end.练习：1.丘比特之剑:在东方男女相爱是千里姻缘一线牵,两人无论身处何处都能相爱,但在西方丘比特之剑射程有限,只有射程内的男女两人才能相爱,求最大缘分和。输入文件：第一行是一个正整数k，表示丘比特的射程。第二行为正整数n（n30),第三到n+2行是男人的姓名和位置坐标,第n+3到第2n+2行是女人的姓名和位置坐标:格式是namexy。剩下的部分是男人和女人间的缘分值p格式为name1name2p，以End作为文件的结束标志，其中姓名字符串的长度不超过20，p=255,每两人之间的缘分值只描述一次,没描述的缘分值为1。输出文件:只有一个数,最大的缘分和的值。2.最少皇后控制在国际象棋中，皇后能向八个方向攻击(如图4-5所示，图中黑点格子为皇后的位置，标有K的格子为皇后可攻击到的格子)。现在给定一个M*N(N、M均不大于10)的棋盘，棋盘上某些格子有障碍。每个皇后被放置在无障碍的格子中，且它就控制了这个格子，除此，它可以从它能攻击到的最多8个格子中选一个格子来控制，如图4-5(b)所示，标号为1的格子被一个皇后所控制。请你编一程序，计算出至少有多少个皇后才能完全控制整个棋盘。输入格式：输入文件的第一行