二分图及二分图匹配及并查集

1、二分图及其二分图的匹配如果可以以某一种方式将题目中的对象分成两个互补的集合，而需要求得他们之间满足某种条件的“一一对应”关系时，往往可以抽象出对象以及对象之间的关系，构造二分图，然后利用匹配算法来解决。这类题目通常需要考察选手构建二分图模型、设计匹配算法、并对其算法进行适当优化等方面的能力。通过DFS判别二分图二分图分成两个顶点子集X和Y。若顶点i属于集合X，则相邻点j必属于集合Y。 proc dfs(d,集合标志); /*从d置入某集合的初始状态出发，判别二分图*/定义d的相邻点u的数据类型; if 非二分图标志 then exit；if d已属于本集合 then exit；if d属于另一

2、集合 then 失败退出;设d的本集合标志;取d的第1个相邻点u；while u存在 do dfs(u,另一集合标志)； ud的下一个相邻点;/* dfs */依次搜索每个无集合标志的顶点i，执行dfs(i,X集合标志)。最后未失败退出的情况，则说明图为二分图。*例题：双栈排序【问题描述】Tom最近在研究一个由趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。操作a：如果输入序列不为空，将第一个元素压入栈S1操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c：如果输入序列不为空，将第一个元素压入栈S2操作d：如果栈S2不为空，将S2栈顶元

3、素弹出至输出序列如果一个1n的排列P可以通过一系列操作使得输出序列为1,2，（n-1），n，Tom就称为P是一个“可双栈排序序列”。例如（1,3,2,4）就是一个“可双栈排序序列”，而（2,3,4,1）不是。下图描述了一个将（1,3,2,4）排序的操作序列：。当然，这样的操作序列有可能有几个，对于上例（1,3,2,4），是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么?【输入】输入文件twostach.in的第一行是一个整数n。第二行有n个用空格隔开的正整数，构成一个1n的排列。【输出】输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字

4、0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。简述题意有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2)。最初的时候,q2,s1和s2都为空,而q1中有n个数(n1000),为1n的某个排列.现在支持如下四种操作:a操作,将 q1的首元素提取出并加入s1的栈顶；b操作,将s1的栈顶元素弹出并加入q2的队列尾；c操作,将 q1的首元素提取出并加入s2的栈顶；d操作,将s2的栈顶元素弹出并加入q2的队列尾；请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,n.如果可以,求出字典序最小的一个操作序列.定理：考虑对于任

5、意两个数qi和qj,它们不能压入同一个栈中的充要条件: 存在一个k,使得ijk且qkqiqi,这显然是不正确的.必要性证明：如果两个数不可以压入同一个栈,那么它们一定满足上述条件。证明逆否命题：也就是如果不满足上述条件,那么这两个数一定可以压入同一个栈. 不满足上述条件有两种情况:情况1：对于任意ijk且qiqi;有两种可能：qkqj或者qkqj时:qi入栈出栈，qj入栈出栈，qk入栈出栈2、qkqj :qi入栈出栈， qj入栈, qk入栈, qk 出栈, qj 出栈结论：若在qk被压入栈前,qi已经被弹出栈，则qk不会对qj产生任何影响。情况2：对于任意iqj.qi入栈，qj入栈， qj出栈

6、，qi出栈这样,原命题的逆否命题得证,所以原命题得证。由此得出有解的判断方法：对所有的数对(i,j)满足1ijn,检查是否存在ijk满足qkqi。1、判断是否有解和任意两个数能否压入同一个栈、对任意两个数qi和qj,若存在一个k,使得ijk且qkqiqj，则这两个数分别入s1栈和s2栈、将s1栈和s2栈中的数字组合成两个顶点子集，同一顶点子集内不会出现任何连边,即不能压入同一个栈的所有数字被分到了两个栈中。任两个不在同一栈的数字间连边。此时我们只考虑检查是否有解,所以只要化O(n)时间检查这个图是不是二分图,就可以得知是否有解了。找字典序最小的解1、确定每个数字入哪个栈，即构造二分图把二分图染

7、成1和2两种颜色,染色为1的结点被压入s1栈, 染色为2结点被压入s2栈。为了字典序尽量小,我们希望让编号小的结点优先压入s1栈。由于二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1，并从它开始DFS染色,直到所有结点都被染色为止。这样,我们就得到了每个结点应该压入哪个栈中。2、从数字1开始，按照目标序列的递增顺序构造操作序列先处理入栈：按照搜索递增顺序每个顶点：若顶点i的颜色为1，则进行a操作，q1i入s1栈；若顶点i的颜色为2，则进行c操作，q1i入s2栈。后处理出栈：若s1栈的栈顶元素为目标序列的当前数字k，则进行b操作，数字k出s1栈

8、；若s2栈的栈顶元素为目标序列的当前数字k，则进行d操作，数字k出s2栈。然后k+1,继续模拟，直至k为n为止。数据结构vara,b,head,next,point,color:array0.2001of longint; /*初始序列为a（对应q1），后缀的最小值序列为b，其中bi= min a k ；邻接表的表首顶点为head，后继指针为next，ikn顶点序列为point，顶点的涂色序列为color*/s:array1.2,0.1000of longint; /*s1栈，栈首指针为s1,0;s2栈, 栈首指针为s2,0*/ n,p,i,j,last:longint; /*序列长度为n，当

9、前应取数字为last*/proc bad ; /*输出失败信息*/ writeln(0);close(output);halt /* bad */proc addedge(a,b:longint); /*（a,b）进入邻接表*/var t:longint; inc(p);pointpb; /*增加顶点b*/if heada=0 /*（a,b）进入邻接表*/then headapelse theada;while nextt0 do tnextt;nexttp ;/*else*/;/* addedge */顶点涂色proc dfs(now:longint);var t:longint;thead

10、now; /*搜索与顶点now相邻的所有顶点*/while t0 do if colorpointt=0 /*若顶点now相邻的顶点pointt未涂色，则该顶点涂互补色，沿该顶点递归下去*/then colorpointt3-colornow;dfs(pointt);/*then*/if colorpointt=colornow /*若顶点now与相邻顶点pointt涂相同色，则失败退出*/ then bad;tnextt; /*访问与顶点now相邻的下一个顶点*/;/*while*/;/*dfs*/构造二分图 assign(input,twostack.in);reset(input); /

11、*输入文件读准备*/assign(output,twostack.out);rewrite(output); /*输出文件写准备*/fillchar(s,sizeof(s),0);fillchar(a,sizeof(a),0); /*两栈空*/readln(n); /*读入排列*/for i1 to n do read(ai);bn+1maxlongint;p0;for in downto 1 do /*计算bi= min a k */ ikn bibi+1;if aibi then biai;/*for*/for i1 to n dofor ji+1 to n doif (bj+1ai)an

12、d(aiaj) /*若ai和aj不能不能压入同一个栈，则(i,j)和(j,i)进入邻接表*/then addedge(i,j);addedge(j,i);/*then*/for i1 to n do /*所有未涂色的顶点涂颜色1，递归*/ if colori=0 then colori1;dfs(i);/*then*/构造操作序列last1; /*目标序列初始化*/for i1 to n do /*模拟输出序列*/ if colori=1 /*ai入s1或s2栈*/then write(a )else write(c );inc(scolori,0);scolori,scolori,0ai;w

13、hile (s1,s1,0=last) or (s2,s2,0=last) do /*将s1或s2栈顶的数字last取出*/ if s1,s1,0=last /*将s1栈顶的last取出*/then write(b );dec(s1,0); /*then*/if s2,s2,0=last /*将s2栈顶的last取出*/then write(d );dec(s2,0); /*then*/inc(last); /*按递增要求取下一个数字*/; /*while*/;/*for*/close(input);close(output);/*关闭输入输出文件*/. /*main*/关押罪犯S城现有两座监

14、狱，一共关押着 N名罪犯，编号分别为 1N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。每年年末，*局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换*局长。在详细考察了 N 名罪犯间的矛盾关系后，*局长觉得压力巨大。

15、他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？【输入】 输入文件名为 prison.in。输入文件的每行中两个数之间用一个空格隔开。 第一行为两个正整数 N和 M，分别表示罪犯的数目以及存在仇恨的罪犯对数。 接下来的 M行每行为三个正整数 aj，bj，cj，表示 aj号和 bj号罪犯之间存在仇恨，其怨气值为 cj。数据保证1aj bj N ，0cj 1,000,000,000，且每

16、对罪犯组合只出现一次。【输出】输出文件 prison.out 共1 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。【数据范围】对于 30%的数据有 N15；对于 70%的数据有 N2000，M50000；对于 100%的数据有 N20000，M100000。第一种方法：思维方向1、能否在同所监狱的最大怨气值不超过c的前提下，将所有罪犯分配在两所监狱。定义图的顶点为罪犯，所有怨气值大于c的罪犯对之间连边，边权为怨气值（连边的两个罪犯不在同一监狱）。如果该图是一个二分图，则顶点集合X和Y的罪犯各分配一个监狱，每个监狱的最大怨气值为c。2、顶点（罪犯）数

17、的上限为20000，边权（怨气值）的数据类型为4个字节的longint，因此不能采用图的相邻矩阵，只能采用指针类型的邻接表存储二分图，采用边表存储原图。3、按照怨气值递增的顺序排序罪犯对。通过二分搜索的办法寻找同一监狱中罪犯对间最小的最大怨气值：算法：二分+判定1、给定一个边权值的顺序值ans，通过二分图判断同一监狱中罪犯对的最大怨气值是 5否不超过ans按照边权递增的顺序排序边集e定义图的顶点为罪犯，存在仇恨的罪犯之间连边，边权为怨气值。将边eansem加入新图中，即这些边的权值不小于第ans大的权值采用dfs或者bfs判定新图是否为一个二分图。若是，则表示新图中任何边(x,y)的端点x和y

18、不能在同一个集合中，同一集合（同一监狱）中罪犯的最大怨气值为eans-1的边权2、枚举边权的大小顺序ans,再通过判定新图是否为二分图来判断能否把罪犯分成两个集合，使得同一集合内罪犯的怨气值不超过第ans大。由于ans是满足单调性的，如果ans可行，则最小的最大怨气值在其左区间，否则最小的最大怨气值在其右区间。所以可以通过二分法来枚举ans。时间复杂度：二分复杂度为O(log(maxci),约为30，判定复杂度为O(m)，故总复杂度为O(log(maxci)*m)。(二分复杂度可以通过离散化进一步降为O(log(n),总复杂度降为O(log(n)*m)数据结构Typerectype=recor

19、d/*存在仇恨的罪犯序号为x、y，怨气值为c*/x,y,c:longint;end;plink=point;/*单链表的指针类型*/point=recordx:longint;next:plink;end; 0顶点i未确定集合var 1顶点i属于x集合 t:array 1.50000 of plink;/*二分图的邻接表*/ 1顶点i属于y集合 c:array1.50000 of longint;/*顶点i的集合标志，ci= - */ e:array 0.200000 of rectype;/*边表，存储存在仇恨的罪犯序列*/n,m:longint; /* 罪犯数为n，存在仇恨的罪犯对数为m*

20、/h:boolean; /*二分图标志*/按照怨气指递增的顺序排列存在仇恨的罪犯对序列eproc sort(l,r:longint);vari,j,v:longint;temp:rectype; il;jr;ve(l+r) div 2.c;repeatwhile ei.cv do dec(j);if ij;if lj then sort(l,j);if ir then sort(i,r);/* sort */proc init;/* 输入信息，按照怨气值递增的顺序排列存在仇恨的罪犯对序列*/var i:longint; readln(n,m);/*读罪犯数和存在仇恨的罪犯对数*/for i1

21、to m do readln(ei.x,ei.y,ei.c);/*读每一对存在仇恨的罪犯序号和怨气值*/ e0.c0;/*虚拟第0对罪犯的怨气值为0*/sort(0,m); /*按照怨气值递增的顺序排列存在仇恨的罪犯对序列e*/;/* init */proc pro(d,r:longint); /*从r集合中的顶点d出发，判别二分图*/var u:plink; if h=false then exit;/*若当前图非二分图，则回溯*/if cd=r then exit;/*若顶点d已属于集合r，则回溯*/if cd=-r then hfalse;exit ;/*若顶点d已属于集合-r，则说明同

22、一集合内的顶点间出现边，返回失败信息*/cdr;utd;/*顶点d设r集合标志，并继续递归下去*/while unil do pro(u.x,-r); uu.next;/* pro */判别第min对罪犯的怨气值是否在同一集合中最大func check(min:longint):boolean;vari:longint;u:plink; for i1 to n do tinil;/*新图初始化为空*/for imin to m do /*将大于等于第min对罪犯的怨气值的罪犯对间连边，构造新图*/ new(u);u.xei.y; u.nexttei.x; tei.xu;new(u);u.xei

23、.x;u.nexttei.y; tei.yu;/*for*/htrue; /*二分图标志初始化*/fillchar(c,sizeof(c),0);/*顶点的集合标志初始化*/for i1 to n do/*从每个未确定集合的顶点出发，判断当前图是否二分图*/ if ci=0 then pro(i,1);if h=false then break ;/*若当前图非二分图，则失败退出*/checkh;/*返回二分图标志*/;/* check */计算和输出冲突事件影响力的最小值proc work;var p,q,ans:longint; p1;qm;while p1.v; repeatwhile

24、ai.vx do dec(j);if ij;/repeatif hej then qsort(he,j);if i0 do9 end; /qsortbeginif find(ai.l)=find(ai.r) then begin ans:=ai.v;break;end; if (duiai.l=0) and(duiai.r=0) then beginduiai.l:=ai.r; duiai.r:=ai.l; end/then begin else beginif duiai.l0 then beginunion(duiai.l,ai.r);if duiai.r=0 then duiai.r:=

25、ai.l; end;/ifif duiai.r0 then beginunion(duiai.r,ai.l);if duiai.l=0 then duiai.l:=ai.r; end;/if end;/else begin dec(i); end;/while writeln(ans); end./main匹配的基本概念设G=V，E一个无向图，ME是G 的若干条边的集合。如果M中的任意两条边没有公共的端点，则称M是G的一个匹配。从给定的图G=V，E的所有匹配中，把包含边数最多的匹配找出来。这种匹配即所谓的最大匹配问题。现实生活中的许多问题可以归结为匹配问题。二分图及二分图的匹配二分图是一种特殊

26、类型的图：图中的顶点集被划分成X与Y两个子集,图中每条边的两个端点一定是一个属于X而另一个属于Y。二分图的匹配是求边的一个子集，该子集中的任意两条边都没有公共的端点。计算二分图最大匹配的匈牙利算法设M是二分图的一个匹配，将M中的边所关联的顶点称为盖点，其余顶点称为未盖点。若一条路径上属于M的边和不属于M的边交替出现，则称该路径为一条交错轨。若路径p是一条起始点和结束点都是未盖点的交错轨，则称p为一条关于M的增广路径，因为通过MMp可使得M中的匹配边数增加1。若二分图中不存在关于M的增广路径，最后得到的匹配M就是G的一个最大匹配。取未盖点t5作为树根，顶点c1是树上第一层中唯一的顶点，未匹配边(

27、t5，c1)是树上的一条边。顶点t2处于树的第二层，边(c1，t2)属于M且关联于c1边，也是树上的又一条边。顶点c5是未盖点可以添加到第三层，找到了一条增广路径p=t5c1t2c5，得到图G的一个更大的匹配Mp，M p是一个完全匹配，从而也是G的一个最大匹配。数据结构const maxn = 200; /*顶点数的上限*/vare:array1.maxn, 0.maxn of integer; /*邻接表，其中顶点i的出度为ei,0，第j条出边的另一端点为ei,j*/link:array1.maxnof integer; /*匹配边集，其中顶点i所在的匹配边为（linki,i）*/ used

28、:array1.maxn of boolean;/*Y集合中顶点的访问标志*/n, m:integer; /* X集和Y集的顶点数各为n,边数为m*/判断是否存在由u出发的可增广路径func check(u:integer):boolean; var i, v:integer; for i1 to eu, 0 do /*枚举u顶点的每一条出边*/ veu,i; /*取出u的第i条出边的另一端点v*/if not usedv /*若v未访问，则访问v*/then usedvtrue;if(linkv=0)or(check(linkv) /*若v的前驱是未盖点或者存在由v的前驱出发的可增广路径，则

29、设定（u,v）为匹配边，返回成功标志*/then linkvu;exit(true); /*then*/;/*then*/;/*for*/exit(false); /*返回失败标志*/;/* check */主程序输入二分图信息，构造邻接表e；最大匹配边数初始化为0；for i1 to n do /*枚举X集的每个顶点*/ fillchar(used,sizeof(used),0);/*Y集合中的所有顶点未访问标志*/if check(i) then 最大匹配边数+1 ;/*for*/输出最大匹配边数;设二分图G有e条边，X集和Y集各有n个顶点，M是G的一个匹配。如果用邻接表表示G，那么求一条

30、关于M的增广路径需要O(e)时间。因为每找出一条新的增广路径都将得到一个更大的匹配，所以最多求n条增广路径就可以求出图G的最大匹配。由此得出，总的时间复杂度为O(n*e) 。多米诺骨牌覆盖给出一个n*n的方阵，但其中有p个点方格被挖掉了，告诉你这些挖去方格的坐标。问是否能用1*2的多米骨牌将剩余的方格恰好覆盖。输入：第1行为方阵规模n；以下为n*n的01矩阵，0代表方格被挖掉；输出：若成功，则输出覆盖剩余方格所使用的多米诺骨牌数；否则输出0。算法分析将所有的方格类似于国际象棋盘一样黑白间隔染色，并在有边相邻的两个（未被挖去的）方格之间连边。很明显，白色的方格之间不可能有边，黑色的方格之间也不可

31、能有边。因此这是一个二分图。而一个多米诺骨牌覆盖的两个方格就相当于一条边覆盖了两个点。因此这就是二分图的最大（完全）覆盖问题。直接用二分图的最大（完全）匹配就可以了。由于这题的图比较特殊，每个方格最多只和4个方格相邻，图的最大边数2n2，因此算法的时间复杂度为O(n4)。(i,j)的黑白判断和顶点序号(i,j)的黑白判断：黑格：行列的奇偶相同（i mod 2=j mod 2）白格：行列的奇偶不同（i mod 2j mod 2）(i,j)的顶点序号k：k=（i-1）*n+j数据结构constmaxn = 50; /*方阵的规模上限*/dx:array1.4of integer=(-1,1,0,0);/*dxi为i方向的水平增量*/dy:array1.4of integer=(0,0,-1,1);/*dyi为i方向的垂直增量*/vare:array1.maxn * maxn, 0.maxn * maxn of integer; /*邻接表，其中顶点i的出度为ei,0，第j条出边的另一端点为ei,j*/link:array1.maxn * maxn of integer