二分圖匹配題目類型總結(jié)

1、二分圖匹配題目類型總結(jié) 二分圖最大匹配的匈牙利算法 二分圖是這樣一個圖，它的頂點可以分類兩個集合X和Y，所有的邊關(guān)聯(lián)在兩個頂點中，恰好一個屬于集合，另一個屬于集合。 最大匹配： 圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。 完美匹配： 如果所有點都在匹配邊上（x=y=m），稱這個最大匹配是完美匹配。最小點覆蓋：(二分圖)最小覆蓋要求用最少的點（集合或集合的都行）讓每條邊都至少和其中一個點關(guān)聯(lián)?？梢宰C明：最少的點（即覆蓋數(shù)）最大匹配數(shù)。支配集：（二分圖）最小點覆蓋數(shù)+孤立點最小邊覆蓋：找最大匹配（注意可能是任意圖最大匹配）m則有2*m 個點被m 條兩兩不相交的邊覆蓋。對于剩下的n-2*m

2、個點，每個點用一條邊覆蓋，總邊數(shù)為n-m條;最小路徑覆蓋：用盡量少的不相交簡單路徑覆蓋有向無環(huán)圖的所有結(jié)點。解決此類問題可以建立一個二分圖模型。把所有頂點i拆成兩個：結(jié)點集中的i和Y結(jié)點集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設(shè)二分圖最大匹配為m,則結(jié)果就是n-m。 最大獨立集問題：(二分圖)n-最小點覆蓋;任意圖最大匹配：（沒有奇環(huán)） 轉(zhuǎn)換為二分圖：把所有頂點i拆成兩個：結(jié)點集中的i和Y結(jié)點集中的i',如果原圖中有邊i->j，則在二分圖中引入邊i->j',j->i；設(shè)二分圖最大匹配為m,則結(jié)果就是m/2。最大完

3、全子圖：補圖的最大獨立集三大博弈問題威佐夫博奕（Wythoff Game）：有兩堆各若干個物品，兩個人輪流從某一堆或同時從兩堆中取同樣多的物品，規(guī)定每次至少取一個，多者不限，最后取光者得勝。 這種情況下是頗為復(fù)雜的。我們用（ak，bk）（ak bk ,k=0，1，2，.,n)表示兩堆物品的數(shù)量并稱其為局勢，如果甲面對（0，0），那么甲已經(jīng)輸了，這種局勢我們稱為奇異局勢。前幾個奇異局勢是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。 可以看出,a0=b0=0,ak是未在前面出現(xiàn)過的最小自然數(shù),而 bk= ak + k，

4、奇異局勢有如下三條性質(zhì)： 1。任何自然數(shù)都包含在一個且僅有一個奇異局勢中。 由于ak是未在前面出現(xiàn)過的最小自然數(shù)，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性質(zhì)1。成立。 2。任意操作都可將奇異局勢變?yōu)榉瞧娈惥謩荨?事實上，若只改變奇異局勢（ak，bk）的某一個分量，那么另一個分量不可能在其他奇異局勢中，所以必然是非奇異局勢。如果使（ak，bk）的兩個分量同時減少，則由于其差不變，且不可能是其他奇異局勢的差，因此也是非奇異局勢。 3。采用適當?shù)姆椒?，可以將非奇異局勢變?yōu)槠娈惥謩荨?假設(shè)面對的局勢是（a,b

5、），若 b = a，則同時從兩堆中取走 a 個物體，就變?yōu)榱似娈惥謩荩?，0）；如果a = ak ，b > bk，那么，取走b - bk個物體，即變?yōu)槠娈惥謩荩蝗绻?a = ak ， b < bk ,則同時從兩堆中拿走 ak - ab - ak個物體,變?yōu)槠娈惥謩荩?ab - ak , ab - ak+ b - ak）；如果a > ak ，b= ak + k,則從第一堆中拿走多余的數(shù)量a - ak 即可；如果a < ak ，b= ak + k,分兩種情況，第一種，a=aj （j < k）,從第二堆里面拿走 b - bj 即可；第二種，a=bj （j < k）

6、,從第二堆里面拿走 b - aj 即可。 從如上性質(zhì)可知，兩個人如果都采用正確操作，那么面對非奇異局勢，先拿者必勝；反之，則后拿者取勝。 那么任給一個局勢（a，b），怎樣判斷它是不是奇異局勢呢？我們有如下公式： ak =k（1+5）/2，bk= ak + k （k=0，1，2，.,n 方括號表示取整函數(shù))奇妙的是其中出現(xiàn)了黃金分割數(shù)（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個物品，兩個人輪流從這堆物品中取物，規(guī)定每次至少取一個，最多取m個。最后取光者得勝。 顯然，如果n=m+1，那么由于一次最多只能取m個，所以，無論先取者拿走多少個，后取者都能夠一次拿走剩余的物品，后者取勝。因此我們發(fā)現(xiàn)了如何取勝的法則：如果n=（m+1）r+s，（r為任意自然數(shù)，sm),那么先取者要拿走s個物品，如果后取者拿走k（m)個，那么先取者再拿走m+1-k個，結(jié)果剩下（m+1）（r-1）個，以后保持這樣的取法，那么先取者肯定獲勝。總之，要保持給對手留下（

8、m+1）的倍數(shù)，就能最后獲勝。 這個游戲還可以有一種變相的玩法：兩個人輪流報數(shù)，每次至少報一個，最多報十個，誰能報到100者勝尼姆博奕（Nimm Game）：有三堆各若干個物品，兩個人輪流從某一堆取任意多的物品，規(guī)定每次至少取一個，多者不限，最后取光者得勝。 這種情況最有意思，它與二進制有密切關(guān)系，我們用（a，b，c）表示某種局勢，首先（0，0，0）顯然是奇異局勢，無論誰面對奇異局勢，都必然失敗。第二種奇異局勢是（0，n，n），只要與對手拿走一樣多的物品，最后都將導(dǎo)致（0，0，0）。仔細分析一下，（1，2，3）也是奇異局勢，無論對手如何拿，接下來都可以變?yōu)椋?，n，n）的情形。 計算機算法里面

9、有一種叫做按位模2加，也叫做異或的運算，我們用符號（+）表示這種運算。這種運算和一般加法不同的一點是1+1=0。先看（1，2，3）的按位模2加的結(jié)果：1 =二進制012 =二進制103 =二進制11 （+）0 =二進制00 （注意不進位） 對于奇異局勢（0，n，n）也一樣，結(jié)果也是0。 任何奇異局勢（a，b，c）都有a（+）b（+）c =0。如果我們面對的是一個非奇異局勢（a，b，c），要如何變?yōu)槠娈惥謩菽兀考僭O(shè) a < b< c,我們只要將 c 變?yōu)?a（+）b,即可,因為有如下的運算結(jié)果: a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要將

10、c 變?yōu)閍（+）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個，變?yōu)椋?9，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)return A.x*(B.y*C.z-B.z*C.y)-A.y*(B.x*C.z-B.z*C.x)+A.z*(B.x*C.y-B.y*C.x);type cross2d(Point A,Point

17、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.z;a=B.y*C.z-B.z*C.y;b=B.x*C.z-B.z*C.x;c=B.x*C.y-B.y*C.x;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 in

18、t &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-11;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<

19、fc;i+) ans+=fabs(cross3d(p0,pfi0,pfi1,pfi2);ans/=6.0;return ans;void ConvexHull()/n>=4,no two points takes the same positionint 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=cr

20、oss3d(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;while(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

21、;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,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,p

22、fj1,pfj2)<eps)break;if(j=i) ans+;return ans;int main()int cas,i,j;/freopen("in.dat","r",stdin);scanf("%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,

23、p+n)-p;ConvexHull();printf("Case %d: %dn",j,countface();/printf("%.4lf %.4lfn",surface(),volume();return 0;Zoj2676 分數(shù)劃分 要求構(gòu)造解#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;dou

24、ble cmaxm,tcmaxm;int bmaxm,opmaxm,nextmaxm;int emaxn,dmaxn,pmaxn,quemaxn,reachmaxn;bool markmaxn;int m,n,s,t,size,ns;double flow,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;mems

25、et(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,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;mems

26、et(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<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

27、(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) /?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 (qu

28、etop=t)sum+=augment(top);else u=quetop;for (;pu>0;pu=nextpu)v=bpu;if (pv>0 && cpu>eps && dv=du+1) break;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

29、,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<<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

30、; 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=mid;create(l);while(connect() && s!=t) flow+=dfs();mincut(l);int main()while(cin>>n>>m)init();netflow();return 0;Pku3246 求給定圖中刪掉一個點后的面積最小的凸包#include <s

31、tdio.h>#include <stdlib.h>#include <math.h>#include <time.h>#define infile "3246.in"#define outfile "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=fop

32、en(infile,"r"),/ *fout=fopen(outfile,"w");FILE *fin=stdin, *fout=stdout;long init() long i,j; struct Tpoint 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

33、 (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 &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-

34、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<-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 (st

35、art<stop) while (start<stop)&&(xiao(x,pstop) stop-; pstart=pstop; if (start<stop) start+; while (start<stop)&&(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);

36、 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 (tbtop>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,pt

37、bi,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,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 (

38、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 Tpoint 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;

39、 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! 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,