hdu 2255二分图最大权值匹配的KM 算法

我的理解：如有错误，请大牛指正！！

1.KM（）算法实际就是一种遍历，从权值最大的开始匹配，如果成功的完备匹配了，那这个权值一定是最大的权值。因为我们是从最大的开始一点点小下来遍历的。

2.slack[ ] 这个数组 可以说是一个 松弛变量数组 ，目的是为了 增加匹配。

3.实际也没什么好讲的就是不断的增广，很多也都这样，松弛迫近，跟那什么单纯形法有想通之处。

4. 匈牙利算法进行匹配的寻找。

hdu 2255

#include
  
   
#include
   
     #include
    
      using namespace std; const int M=400,inf=0x3f3f3f3f; int w[M][M],link[M],lx[M],ly[M]; int nx,ny,n,slack[M]; int visx[M],visy[M]; int DFS(int x){ visx[x]=1; int i; for(i=1;i<=ny;i++){ if(visy[i]) continue; int t=lx[x]+ly[i]-w[x][i]; if(t==0){ visy[i]=1; if(link[i]==-1||DFS(link[i])){ link[i]=x; return 1; } } else if(slack[i]>t) slack[i]=t; } return 0; } int KM() { int i,j; memset(link,-1,sizeof(link)); memset(ly,0,sizeof(ly)); for(i=1;i<=nx;i++) for(j=1,lx[i]=-inf;j<=ny;j++){ if(lx[i]
     
      -1) res+=w[link[i]][i]; } return res; } int main() { int i,j; while(scanf(%d,&n)!=EOF){ nx=ny=n; for(i=1;i<=nx;i++) for(j=1;j<=ny;j++) scanf(%d,&w[i][j]); printf(%d ,KM()); } return 0; }