首页 > 代码库 > Bipartitegraph1325
Bipartitegraph1325
最小点覆盖数： 用最少的点让每一条边都至少和其中的一个点相关联。点数=最大匹配数
二分图的最大匹配有两种求法，第一种是最大流；第二种就是我现在要讲的匈牙利算法。
从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个
假设已经找到匹配边(s,t) (w,v)（此时mark[t]=s,mark[v]=w，说明v,t已经匹配，不能有新的边连接这两个点。实际上mark每次标记的都是右边的点，而不是左边的），此时运行到x点，对于v点由于mark!=0，说明已经参与匹配，所以(x,v)已经不能当做一个新的匹配边(二分匹配的定义是最多一条边连接一个顶点)。于是考虑dfs(mark[v])，即dfs(w)，观察w周围能不能找到一个匹配边y，从而使得y,(w,v),(v,x)构成新的增广路，从而得到新的匹配边。但是w周围只有t节点，并且t节点已经被匹配，因此考虑dfs(mark[z])，即dfs(s)，找到z点，从而（z,s）(s,t) (t,w) (w,v) (v,x)（蓝色的表示已匹配，黑色是未匹配）构成新的增广路，此时回朔，运行mark[z]=s,return 1,从dfs(s)回到dfs(w),mark[t]=w(w从dfs(mark[t])出去的),再回到dfs(x)，得到mark[v]=x，回到主循环max加1，此时mark[w]仍然为0，不过没关系，因为考察的mark都是考察右边节点的mark，考察左边节点的时候都是遍历左边节点与周围节点的关系。
#include<iostream>#include<cstring>#include<cstdio>using namespace std;#define N 150int visit[N];int mark[N];int match[N][N];int n,m,k;int dfs(int x){ int i;for(i=1+n;i<=1+n+m;i++)for(i=1;i<=m;i++)//可以不用上面的方式，因为visit,mark都是针对右边节点的，不会影响左边，而map仅仅是标记作用。 { if(!visit[i]&&match[x][i]) { visit[i]=1;//标记检查过的点,visit是全局的，这一次不成功，以后哪怕换一个起点经过改点的时候一定还是不会成功。 if(!mark[i]||dfs(mark[i]))//如果在x周围找到还没匹配过的点，说明找到一条之前没有匹配的边，把该改边通过改变mark[i]从而该边标记为已经匹配。如果该边已经被匹配，那么没关系，只要该节点的父节点还能找到一边新的未匹配的点（前面父节点找到一个就RETURN结束了，因此可能还有可以匹配的点构成新的匹配边，如上图所示：） { mark[i]=x;//修改匹配关系 return 1; } } } return 0;}int main(){ int i,j; while(cin>>n>>m>>k && n) { memset(mark,0,sizeof(mark)); memset(match,0,sizeof(match)); for(i=1;i<=k;i++) { int a,b; cin>>a>>b; match[a][b]=1;//标记当前匹配关系下面这种方式没有必要//map[x][y+n]=1; } int max=0; for(j=1;j<=n;j++)//如果从一个点A出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从A出发都永远找不到增广路径。 { memset(visit,0,sizeof(visit));//每轮匹配请0 if(dfs(j)) max++; } cout<<max<<endl; } return 0;}
Bipartitegraph1325