二分图匹配题目类型总结

1、二分图匹配题目类型总结 二分图最大匹配的匈牙利算法 二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合，另一个属于集合。 最大匹配： 图中包含边数最多的匹配称为图的最大匹配。 完美匹配： 如果所有点都在匹配边上（x=y=m），称这个最大匹配是完美匹配。最小点覆盖：(二分图)最小覆盖要求用最少的点（集合或集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）最大匹配数。支配集：（二分图）最小点覆盖数+孤立点最小边覆盖：找最大匹配（注意可能是任意图最大匹配）m则有2*m 个点被m 条两两不相交的边覆盖。对于剩下的n-2*m

2、个点，每个点用一条边覆盖，总边数为n-m条;最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图的所有结点。解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m。 最大独立集问题：(二分图)n-最小点覆盖;任意图最大匹配：（没有奇环） 转换为二分图：把所有顶点i拆成两个：结点集中的i和Y结点集中的i',如果原图中有边i->j，则在二分图中引入边i->j',j->i；设二分图最大匹配为m,则结果就是m/2。最大完

3、全子图：补图的最大独立集三大博弈问题威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。 这种情况下是颇为复杂的。我们用（ak，bk）（ak bk ,k=0，1，2，.,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。 可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，

4、奇异局势有如下三条性质： 1。任何自然数都包含在一个且仅有一个奇异局势中。 由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。 2。任意操作都可将奇异局势变为非奇异局势。 事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。 3。采用适当的方法，可以将非奇异局势变为奇异局势。 假设面对的局势是（a,b

5、），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b - bk个物体，即变为奇异局势；如果 a = ak ， b < bk ,则同时从两堆中拿走 ak - ab - ak个物体,变为奇异局势（ ab - ak , ab - ak+ b - ak）；如果a > ak ，b= ak + k,则从第一堆中拿走多余的数量a - ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，a=aj （j < k）,从第二堆里面拿走 b - bj 即可；第二种，a=bj （j < k）

6、,从第二堆里面拿走 b - aj 即可。 从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。 那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式： ak =k（1+5）/2，bk= ak + k （k=0，1，2，.,n 方括号表示取整函数)奇妙的是其中出现了黄金分割数（1+5）/2 = 1。618.,因此,由ak，bk组成的矩形近似为黄金矩形，由于2/（1+5）=（5-1）/2，可以先求出j=a（5-1）/2，若 a=j（1+5）/2，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+

7、1+ j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。 显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，sm),那么先取者要拿走s个物品，如果后取者拿走k（m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（

8、m+1）的倍数，就能最后获胜。 这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜尼姆博奕（Nimm Game）：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。 这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。 计算机算法里面

9、有一种叫做按位模2加，也叫做异或的运算，我们用符号（+）表示这种运算。这种运算和一般加法不同的一点是1+1=0。先看（1，2，3）的按位模2加的结果：1 =二进制012 =二进制103 =二进制11 （+）0 =二进制00 （注意不进位） 对于奇异局势（0，n，n）也一样，结果也是0。 任何奇异局势（a，b，c）都有a（+）b（+）c =0。如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b< c,我们只要将 c 变为 a（+）b,即可,因为有如下的运算结果: a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要将

10、c 变为a（+）b，只要从 c中减去 c-（a（+）b）即可。 例1。（14，21，39），14（+）21=27，39-27=12，所以从39中拿走12个物体即可达到奇异局势（14，21，27）。 例2。（55，81，121），55（+）81=102，121-102=19，所以从121中拿走19个物品就形成了奇异局势（55，81，102）。 例3。（29，45，58），29（+）45=48，58-48=10，从58中拿走10个，变为（29，45，48）。 例4。我们来实际进行一盘比赛看看： 甲7,8,9)->(1,8,9)奇异局势 乙1,8,9)->(1,8,4) 甲1,8,4)-

11、>(1,5,4)奇异局势 乙1,5,4)->(1,4,4) 甲1,4,4)->(0,4,4)奇异局势 乙0,4,4)->(0,4,2) 甲0.4,2)->(0,2,2)奇异局势 乙0,2,2)->(0,2,1) 甲0,2,1)->(0,1,1)奇异局势 乙0,1,1)->(0,1,0) 甲0,1,0)->(0,0,0)奇异局势 甲胜。Convex Hull 3D描述Given n points in 3D space, count the number of faces of their convex hull. In the convex

12、 hull, no two faces can be coplanar. 输入The first line contains a single integer T (1 T 100), the number of test cases. Each test case begins with a line containing a single integer n (4 n 1000), the number of points.In the following n lines, each contains three integers x, y, z (-1000 x, y, z 1000),

13、 the coordinates of each point.输出For each test case, print the case number and the number of faces. If the convex hull is empty (all the points lie in a single plane), output 0. 样例输入3 4 1 0 0 0 1 0 0 0 1 0 0 0 4 0 0 0 0 1 0 1 1 0 1 0 0 9 0 0 0 0 2 0 2 2 0 2 0 0 0 0 2 0 2 2 2 2 2 2 0 2 1 1 1 样例输出Case

14、 1: 4 Case 2: 0 Case 3: 6 #include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#include <algorithm>#include <vector>using namespace std;#define type doubleconst int maxn=1005;const int notexist=-1;const double eps=1e-8;struct Pointtype x,y,z;vo

15、id operator-=(Point other)x=x-other.x;y=y-other.y;z=z-other.z;bool operator<(Point other)constif(x!=other.x) return x<other.x;if(y!=other.y) return y<other.y;return z<other.z;bool operator=(Point other)constreturn fabs(x-other.x)+fabs(y-other.y)+fabs(z-other.z)<eps;Point pmaxn; /store

16、 the set of pointsint n;/number of pointsint f10*maxn3; /store the facesint fc;/number of facesbool Rmaxnmaxn;/(i,j,Rij) is a facetype delta3d(const Point &A,const Point &B,const Point &C)type cross2d(Point A,Point B,Point C)type a,b,c;B.x-=A.x;B.y-=A.y;B.z-=A.z;C.x-=A.x;C.y-=A.y;C.z-=A.

17、z;return sqrt(a*a+b*b+c*c);type cross3d(Point A,Point B,Point C,Point D)B-=A;C-=A;D-=A;return delta3d(B,C,D);inline void addface(const int &pa,const int &pb,const int &pc)/(pa,pb,pc)ffc0=pa;ffc1=pb;ffc+2=pc;inline void delface(int i) /remove relation (pa,pb,pc) from Rfi0=ffc-10;fi1=ffc-1

18、1;fi2=ffc-12;fc-;double surface()int i;double ans=0;for(i=0;i<fc;i+) ans+=fabs(cross2d(pfi0,pfi1,pfi2);ans/=2.0;return ans;double volume()int i;double ans=0;for(i=0;i<fc;i+) ans+=fabs(cross3d(p0,pfi0,pfi1,pfi2);ans/=6.0;return ans;void ConvexHull()/n>=4,no two points takes the same position

19、int i,k,h,j;type t;fc=0;/set the number of faces to zerofor(i=2;i<n;i+) if(fabs(cross2d(p0,p1,pi)>eps)swap(p2,pi);break;if(i=n) return ;for(i=3;i<n;i+) if(fabs(t=cross3d(p0,p1,p2,pi)>eps)swap(p3,pi);break;if(i=n) return ;addface(0,1,2);addface(2,1,0);for(k=3;k<n;k+)i=0;bool flag=0;whi

20、le(i<fc) if(cross3d(pk,pfi0,pfi1,pfi2)<-eps)flag=1;Rfi0fi1=1;Rfi1fi2=1;Rfi2fi0=1;delface(i);elseRfi0fi1=0;Rfi1fi2=0;Rfi2fi0=0;i+;if(!flag) continue;h=fc;for(i=0;i<h;i+) if(!Rfi0fi1)if(Rfi1fi0)addface(fi1,fi0,k);if(Rfi2fi1)addface(fi2,fi1,k);if(Rfi0fi2)addface(fi0,fi2,k);int countface()int i

21、,j,ans=0;for(i=0;i<fc;i+)for(j=0;j<i;j+)if(fabs(cross3d(pfi0,pfj0,pfj1,pfj2)<eps&&fabs(cross3d(pfi1,pfj0,pfj1,pfj2)<eps&&fabs(cross3d(pfi2,pfj0,pfj1,pfj2)<eps)break;if(j=i) ans+;return ans;int main()int cas,i,j;/freopen("in.dat","r",stdin);scanf(&qu

22、ot;%d",&cas);for(j=1;j<=cas;j+)scanf("%d",&n);for(i=0;i<n;i+) scanf("%lf%lf%lf",&pi.x,&pi.y,&pi.z);sort(p,p+n);n=unique(p,p+n)-p;ConvexHull();printf("Case %d: %dn",j,countface();/printf("%.4lf %.4lfn",surface(),volume();return 0;

23、Zoj2676 分数划分 要求构造解#include <iostream>using namespace std;const int maxn=200;const int maxm=1000;const double eps=1e-12;const double dps=1e-6;const double maxw=1e11;double cmaxm,tcmaxm;int bmaxm,opmaxm,nextmaxm;int emaxn,dmaxn,pmaxn,quemaxn,reachmaxn;bool markmaxn;int m,n,s,t,size,ns;double flo

24、w,value;double min(double a,double b)return a<b?a:b;void addedge(int u,int v,double x,int p)size+;nextsize=eu;eu=size;csize=x;bsize=v;opsize=p;void init()int i,a,b,x;memset(e,-1,sizeof(e);s=1; t=n; ns=t+1; size=0;for (i=1;i<=m;i+)scanf("%d%d%d",&a,&b,&x);tci=x;addedge(a,b

25、,x,size+2);addedge(b,a,x,size);void create(double g)int i;double x;flow=value=0;for (i=1;i<=m;i+)x=tci-g;if (x<0) value+=x;c2*i-1=c2*i=x;bool connect()int i,j,l,r;memset(que,0,sizeof(que);memset(mark,0,sizeof(mark);for (i=0;i<=ns;i+) di=ns;ds=0;que1=s; l=0; r=1; marks=true;l=0; r=1;while(l&

26、lt;r)i=que+l;for (j=ei;j>0;j=nextj)if (!markbj && cj>eps)markbj=true;que+r=bj;dbj=di+1;return (dt<ns);double augment(int &top)int i;double x;x=maxw;for (i=top;i>=2;i-) x=min(x,cpquei-1);if (x<eps) return 0;for (i=top;i>=2;i-)cpquei-1-=x;coppquei-1+=x;if (cpquei-1<eps

27、) /?top=i-1;pquei-1=nextpquei-1;return x;double dfs()int i,u,v,top;double sum;memset(que,0,sizeof(que);for (i=0;i<=ns;i+) pi=ei;que1=s; top=1; sum=0;while(top>0)if (quetop=t)sum+=augment(top);else u=quetop;for (;pu>0;pu=nextpu)v=bpu;if (pv>0 && cpu>eps && dv=du+1) brea

28、k;if (pu<=0) top-;else que+top=v;return sum;void dfss(int u)int i;if (reachu) return ;reachu=1;for (i=eu;i>0;i=nexti)if (ci>eps) dfss(bi);void mincut(double g)int i,num;memset(reach,0,sizeof(reach);dfss(s);num=0;for (i=1;i<=m;i+)if (reachb2*i reachb2*i-1) | (tci-g<=0) num+;cout<<

29、;num<<endl;for (i=1;i<=m;i+)if (reachb2*i reachb2*i-1) | (tci-g<=0) printf("%d ",i);printf("nn");void netflow()double l,r,mid;r=10000000; l=0; while(r-l>dps)mid=(l+r)/2;create(mid);while(connect() && s!=t)flow+=dfs();if (flow+value/2>eps) l=mid; else r=m

30、id;create(l);while(connect() && s!=t) flow+=dfs();mincut(l);int main()while(cin>>n>>m)init();netflow();return 0;Pku3246 求给定图中删掉一个点后的面积最小的凸包#include <stdio.h>#include <stdlib.h>#include <math.h>#include <time.h>#define infile "3246.in"#define outf

31、ile "3246.out"const long maxn = 100010;const double zero = 1e-9;struct Tpoint double x,y;pmaxn+1;long tbmaxn+1,qqmaxn+1, n,tbtop,qqtop;double result;/FILE *fin=fopen(infile,"r"),/ *fout=fopen(outfile,"w");FILE *fin=stdin, *fout=stdout;long init() long i,j; struct Tpoint

32、 t; fscanf(fin,"%ld",&n); if (!n) return 0; j=1; for (i=1; i<=n; i+) fscanf(fin,"%lf%lf",&pi.x,&pi.y); if (pi.y<pj.y-zero) j=i; else if (pi.y<pj.y+zero)&&(pi.x<pj.x) j=i; t=p1; p1=pj; pj=t; return 1;double cj(struct Tpoint &p0,struct Tpoint &am

33、p;p1,struct Tpoint &p2) return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);double jl(struct Tpoint &a,struct Tpoint &b) return (sqrt(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);long xiao(struct Tpoint &a,struct Tpoint &b) double t; t=cj(p1,a,b); if (t>zero) return 1; if (t<-

34、zero) return 0; return (jl(p1,a)<jl(p1,b);void pass(long start,long stop,long &mid) struct Tpoint x; long t; t=rand()%(stop-start+1)+start; x=pt; pt=pstart; while (start<stop) while (start<stop)&&(xiao(x,pstop) stop-; pstart=pstop; if (start<stop) start+; while (start<stop

35、)&&(xiao(pstart,x) start+; pstop=pstart; if (start<stop) stop-; mid=start; pmid=x;void px(long start,long stop) long mid; if (start<stop) pass(start,stop,mid); px(start,mid-1); px(mid+1,stop); void calc_tb() long i; for (i=1; i<=3; i+) tbi=i; tbtop=3; for (i=4; i<=n; i+) while (t

36、btop>1)&&(cj(ptbtbtop-1,ptbtbtop,pi)<-zero) tbtop-; tb+tbtop=i; void calc_result() long i,j; double area=0,now; for (i=2; i<tbtop; i+) area+=fabs(cj(ptb1,ptbi,ptbi+1); pn+1=p1; tbtbtop+1=n+1; area/=2; /Don't forget! result=1e20; for (i=2; i<=tbtop; i+) now=area-fabs(cj(ptbi-1

37、,ptbi,ptbi+1)/2; qqtop=1; qq1=tbi-1; for (j=tbi-1+1; j<=tbi+1; j+) if (j!=tbi) while (qqtop>1)&&(cj(pqqqqtop-1,pqqqqtop,pj)<-zero) qqtop-; qq+qqtop=j; for (j=2; j<qqtop; j+) now+=fabs(cj(pqq1,pqqj,pqqj+1)/2; if (now<result) result=now; void calc_result_2() long i,j; struct Tpo

38、int t; double area; for (i=1; i<n; i+) pi=pi+1; n-; j=1; for (i=1; i<=n; i+) if (pi.y<pj.y-zero) j=i; else if (pi.y<pj.y+zero)&&(pi.x<pj.x) j=i; t=p1; p1=pj; pj=t; px(2,n); calc_tb(); area=0; for (i=2; i<tbtop; i+) area+=fabs(cj(ptb1,ptbi,ptbi+1); area/=2; /Don't forget

39、! if (area<result) result=area;void work() long i; px(2,n); calc_tb(); calc_result(); calc_result_2(); /delete point 1void output() fprintf(fout,"%.2lfn",result);int main() srand(time(0); while (init() work(); output(); return 0;Pku2125 给定删一个点的所有入边的代价，和所有初边的代价，要求把图破坏代价最小#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int mx = 300;const int inf = (1 << 30);int cmxmx, opmx, dmx, lstmx, tp, L, R, N, M, S, T,