先把最基础的概念搞清楚：
二分图：有两组顶点，一组顶点记为 S1 ，另一组记为 S2 ， S1 和 S2 没有公共的元素，并且所有的边都是连接 S1 和 S2 中的点的，对于 S1 和 S2 本身，它们内部的任何两个点都没有边相连，这样的无向图就叫二分图。
点覆盖集：即是一个点集，使得所有边至少有一个端点在集合里。
边覆盖集：即是一个边集，使得所有点都与集合里的边邻接。（其实我觉得这句话很难理解）
但是结合这句呢：在一个P*P的有向图中，最小路径覆盖＝｜Ｐ｜－最大匹配数。（因为有匹配数的存在，本来要P个边的覆盖因此减小了）
二分图的最小顶点覆盖数等于最大匹配数。
匈牙利算法：主要二分图的最大匹配数。其实我觉得自学这东西不适合我，可能以前而到现在仍受体制化的影响，有老师真好（有依赖感了）。。并且我觉得有些自己理解花的时间比别人讲的时间要多很多很多！！！
等等。。。
除了点覆盖数还有边覆盖数。。。
下面M是G的一个匹配。
M-交错路：p是G的一条通路，如果p中的边为属于M中的边与不属于M但属于G中的边交替出现，则称p是一条M-交错路。
M-饱和点：对于v∈V(G），如果v与M中的某条边关联，则称v是M-饱和点，否则称v是非M-饱和点。
M-可增广路：p是一条M-交错路，如果p的起点和终点都是非M-饱和点，则称p为M-可增广路。（不要和流网络中的增广路径弄混了）
匈牙利算法：（用于求最大匹配数）
COURSES POJ 1469
一道匈牙利算法的模板题：
1 #include<iostream> 2 #include<algorithm> 3 #include<stdio.h> 4 #include<string.h> 5 using namespace std; 6 int a[110][310];//邻接矩阵。用来存储边的信息，连接或没连接 7 int vis[310],b1[310],m;//一个用来搜索的标记，一个记录点匹配点的编号 8 int dfs(int x) 9 { 10 int i; 11 for(i=1;i<=m;i++) 12 if(a[x][i]&&!vis[i])//连通了并且没被标记 13 { 14 vis[i]=1;//进行标记 15 if(b1[i]==0||dfs(b1[i]))//没有被匹配或者前面的有增广路 16 { 17 b1[i]=x;//进行记录 18 return 1;//返回能匹配 19 } 20 } 21 return 0;//返回没有被匹配 22 } 23 int main() 24 { 25 int t,n,i,j,a2,a1,s; 26 scanf("%d",&t); 27 while(t--) 28 { 29 memset(a,0,sizeof(a)); 30 scanf("%d%d",&n,&m); 31 for(i=1;i<=n;i++) 32 { 33 scanf("%d",&a1); 34 while(a1--) 35 { 36 scanf("%d",&a2); 37 a[i][a2]=1; 38 } 39 } 40 s=0; 41 memset(b1,0,sizeof(b1)); 42 for(i=1;i<=n;i++) 43 { 44 memset(vis,0,sizeof(vis));//每次都要更新 45 if(dfs(i)) 46 s++; 47 } 48 if(s==n) 49 printf("YES "); 50 else 51 printf("NO "); 52 } 53 return 0; 54 }
再就是求最小顶点覆盖数：（因为理论上就等于最大匹配数）
Asteroids POJ 3041
直接上匈牙利算法求最大匹配数就行了。。。
1 #include<iostream> 2 #include<algorithm> 3 #include<stdio.h> 4 #include<string.h> 5 using namespace std; 6 int a[505][505],vis[505],b1[505],n; 7 int dfs(int x) 8 { 9 int i; 10 for(i=1;i<=n;i++) 11 { 12 if(a[x][i]&&!vis[i]) 13 { 14 vis[i]=1; 15 if(b1[i]==0||dfs(b1[i])) 16 { 17 b1[i]=x; 18 return 1; 19 } 20 } 21 } 22 return 0; 23 } 24 int main() 25 { 26 int m,a1,a2,s,i; 27 while(scanf("%d%d",&n,&m)!=EOF) 28 { 29 memset(a,0,sizeof(a)); 30 while(m--) 31 { 32 scanf("%d%d",&a1,&a2); 33 a[a1][a2]=1; 34 } 35 memset(b1,0,sizeof(b1)); 36 s=0; 37 for(i=1;i<=n;i++) 38 { 39 memset(vis,0,sizeof(vis)); 40 if(dfs(i)) 41 s++; 42 } 43 printf("%d ",s); 44 } 45 return 0; 46 }
之后就是求最大权匹配：KM算法。。。
本人觉得有好多细节部分需要多次编写与记忆！
突出的一点要用顶标来计算，于是乎就多了两个数组，之后再交错树那里又多了一个数组！
然而判断方面因为有两顶标，就又多了一个数组。。。算算要开7个数组吧！！！（其中有两对）
奔小康赚大钱 HDU 2255
思路具体参见：http://www.cnblogs.com/jackge/archive/2013/05/03/3057028.html
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 int vix[310],viy[310],link[310],a[310][310],lx[310],ly[310],nx,ny,slack[310]; 7 int inf=1000005; 8 int dfs(int x)//跟匈牙利算法差不多 9 { 10 int i,temp; 11 vix[x]=1;//不同点 12 for(i=1;i<=ny;i++) 13 { 14 if(viy[i]) 15 continue; 16 temp=lx[x]+ly[i]-a[x][i];//找的是相等子图 17 if(temp==0) 18 { 19 viy[i]=1; 20 if(link[i]==-1||dfs(link[i])) 21 { 22 link[i]=x; 23 return 1; 24 } 25 } 26 else if(slack[i]>temp) 27 slack[i]=temp; 28 } 29 return 0; 30 } 31 int main() 32 { 33 int i,j,s,n; 34 while(scanf("%d",&n)!=EOF) 35 { 36 nx=ny=n; 37 for(i=1;i<=n;i++) 38 for(j=1;j<=n;j++) 39 scanf("%d",&a[i][j]); 40 memset(lx,0,sizeof(lx)); 41 memset(ly,0,sizeof(ly)); 42 memset(link,-1,sizeof(link)); 43 for(i=1;i<=nx;i++) 44 for(j=1;j<=ny;j++) 45 if(a[i][j]>lx[i]) 46 lx[i]=a[i][j]; 47 for(i=1;i<=nx;i++) 48 { 49 for(j=1;j<=nx;j++) 50 slack[j]=inf; 51 while(1) 52 { 53 memset(vix,0,sizeof(vix));//记录搜索的每次都更新 54 memset(viy,0,sizeof(viy));//如上 55 if(dfs(i))//有匹配 56 break; 57 int d=inf;//下面是核心：凑成一个匹配出来 58 for(j=1;j<=ny;j++) 59 if(!viy[j]&&d>slack[j]) 60 d=slack[j]; 61 for(j=1;j<=nx;j++) 62 if(vix[j]) 63 lx[j]-=d; 64 for(j=1;j<=ny;j++) 65 if(viy[j]) 66 ly[j]+=d; 67 else 68 slack[j]-=d; 69 } 70 } 71 s=0; 72 for(i=1;i<=ny;i++) 73 if(link[i]!=-1) 74 s+=a[link[i]][i]; 75 printf("%d ",s); 76 } 77 return 0; 78 }
经过渊神的细心指导，总算弄懂清楚不少了！在此十分感谢！！！
根据KM算法，找不到匹配时，就要用交错树来凑成一个！（当然希望每进行一次，能凑成一个。。。于是就有slack[]数组了）
vix[]与viy[]是判断是否在交错树中的。。。
根据算法：在树中的lx[]减d，ly[]加d。。。（当然这个值d得在交错树外面找啊，因为进入交错树的都是有匹配的。。。）
最关键的：因为呢，slack[j] = lx[i] + ly[j] - w[i][j]，而lx[]减小，其他的不变，（ly[]是交错树外面的），那么slack[j]也要减小d了。。。
时刻谨记着二分图是以左边为基点，向右边进行查找的（一旦左边的向下移动了，必定已经找到了。。。）
之后我发现求最大权匹配和最小权匹配是多么的不同啊！！
在建图的时候，（将每条边的权值变为负数。然后lx[i]初始化为-INT_MAX，结果输出-ans）！！，就可以得到最小权值。
这句话的重点在：要非常大啊！！
Going Home HDU1533
废话也不说了，先化成二分图的形式。。。之后慢慢比对上面的代码！
1 #include<iostream> 2 #include<algorithm> 3 #include<stdio.h> 4 #include<math.h> 5 #include<string.h> 6 using namespace std; 7 int vix[105],viy[105],link[105],b[105][105],lx[105],ly[105],d,slack[105]; 8 int inf=100000005;//要非常大，少个零就超时！！ 9 struct line 10 { 11 int x; 12 int y; 13 }a1[105],b1[105]; 14 int dfs(int x)//跟匈牙利算法差不多 15 { 16 int i,temp; 17 vix[x]=1;//不同点 18 for(i=1;i<=d;i++) 19 { 20 if(viy[i]) 21 continue; 22 temp=lx[x]+ly[i]-b[x][i];//找的是相等子图 23 if(temp==0) 24 { 25 viy[i]=1; 26 if(link[i]==-1||dfs(link[i])) 27 { 28 link[i]=x; 29 return 1; 30 } 31 } 32 else if(slack[i]>temp) 33 slack[i]=temp; 34 } 35 return 0; 36 } 37 int main() 38 { 39 char a[105][105]; 40 int i,n,m,d1,j,s; 41 while(scanf("%d%d",&n,&m)!=EOF) 42 { 43 if(m==0&&n==0) 44 break; 45 for(i=0;i<n;i++) 46 scanf("%s",a[i]); 47 d=0;d1=0; 48 for(i=0;i<n;i++) 49 for(j=0;j<m;j++) 50 { 51 if(a[i][j]=='m') 52 { 53 d++; 54 a1[d].x=i; 55 a1[d].y=j; 56 } 57 if(a[i][j]=='H') 58 { 59 d1++; 60 b1[d1].x=i; 61 b1[d1].y=j; 62 } 63 } 64 for(i=1;i<=d;i++) 65 for(j=1;j<=d;j++) 66 b[i][j]=-abs(a1[i].x-b1[j].x)-abs(a1[i].y-b1[j].y);//全变成负值 67 memset(lx,-inf,sizeof(lx));//这里初始为负的，因为下面是负值，你要求较大值。。不然全为零了 68 memset(ly,0,sizeof(ly)); 69 memset(link,-1,sizeof(link)); 70 for(i=1;i<=d;i++) 71 for(j=1;j<=d;j++) 72 if(b[i][j]>lx[i])//赋负值的原因 73 lx[i]=b[i][j]; 74 for(i=1;i<=d;i++) 75 { 76 for(j=1;j<=d;j++) 77 slack[j]=inf; 78 while(1) 79 { 80 memset(vix,0,sizeof(vix));//记录搜索的每次都更新 81 memset(viy,0,sizeof(viy));//如上 82 if(dfs(i))//有匹配 83 break; 84 int h=inf;//下面是核心：凑成一个匹配出来 85 for(j=1;j<=d;j++) 86 if(!viy[j]&&h>slack[j]) 87 h=slack[j]; 88 for(j=1;j<=d;j++) 89 { 90 if(vix[j]) 91 lx[j]-=h; 92 if(viy[j]) 93 ly[j]+=h; 94 else 95 slack[j]-=h; 96 } 97 } 98 } 99 s=0; 100 for(i=1;i<=d;i++) 101 s+=b[link[i]][i]; 102 printf("%d ",-s); 103 104 } 105 return 0; 106 }