图论相关之匈牙利算法

  这个本来应该是在大一就掌握的算法，硬生生被我拖到现在。。。

　匈牙利算法是用来求二分图的最大匹配的一种比较简单的算法，最核心的东西就是找增广路径。详情： http://blog.csdn.net/acdreamers/article/details/8621130

　　记住一些常见的结论：

　　(1)二分图的最小顶点覆盖 

　　最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。

　　Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。

 

　　(2)DAG图的最小路径覆盖  

　　用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。

　　结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）

　　(3)二分图的最大独立集

　　最大独立集问题： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值

　　结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）

匈牙利算法模板：

bool dfs(int x) {
	for(int j=0; j<n; j++) {
		if( Map[x][j] && !vis[j] ) {
			vis[j] = true;
			if( link[j]==-1 || dfs(link[j]) ) {
				link[j] = x;
				return true;
			}
		}
	}
	return false;
} 

void solve() {
	int res = 0;
	CLS(link, -1);
	for(int i=0; i<n; i++) {
		CLS(vis, false);
		if( dfs(i) ) res ++;
	}
	//这个res便是最大匹配数
}

 

 再加几个模板题吧！ http://acm.hdu.edu.cn/showproblem.php?pid=1150

这个是求最小顶点覆盖~

 //  Asimple
 #include <bits/stdc++.h>
 #define  INF 0xffffff
 #define  mod 1000000
 #define  swap(a, b, t) t = a, a = b, b = t
 #define  CLS(a, v) memset(a, v, sizeof(a))
 #define  debug( a )  cout << #a << " = "  << a <<endl
 #define  abs(x) x<0?-x:x
 #define  srd(a) scanf("%d", &a)
 #define  src(a) scanf("%c", &a)
 #define  srs(a) scanf("%s", a)
 #define  srdd(a, b) scanf("%d %d",&a, &b)
 #define  srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
 #define  prd(a) printf("%d\n", a)
 #define  prdd(a, b) printf("%d %d\n",a, b)
 using   namespace   std;
typedef   long   long   ll;
  const   int  maxn =  1005  ; 
 int   n, m, num, T, k, x, y, len, ans;
  int   endx, endy, t; 
 int   Map[maxn][maxn]; 
 bool   vis[maxn];
  int   link[maxn]; 

 bool  dfs( int   x) {
      for ( int  j= 0 ; j<m; j++ ) {
          if ( Map[x][j] && ! vis[j] ) {
            vis[j]  =  true  ;
              if ( link[j]==- 1  ||  dfs(link[j]) ) {
                link[j]  =  x;
                  return   true  ;
            }
        }
    }
      return   false  ;
} 

  void   solve() {
      int  res =  0  ;
    CLS(link,  - 1  );
      for ( int  i= 0 ; i<n; i++ ) {
        CLS(vis,   false  );
          if ( dfs(i) ) res ++ ;
    }
    prd(res);
}

  void   input() {
      while ( ~srd(n) &&  n ) {
        srdd(m, num);
        memset(Map,   0 ,  sizeof  (Map));
          for ( int  i= 0 ; i<num; i++ ) {
            srddd(x, x, y);
              if ( x&&y ) Map[x][y] =  1  ;
        }
        solve();
    }
}

  int   main(){
    input();
      return   0  ;
} 

第二个： http://acm.hdu.edu.cn/showproblem.php?pid=1068

求最小路径覆盖数。由于本题是双向图，所以最小 路径覆盖数 等于顶点数n双向图的最大匹配/2

 //  Asimple 
#include <bits/stdc++.h>
 #define  INF 0xffffff
 #define  mod 1000000
 #define  swap(a, b, t) t = a, a = b, b = t
 #define  CLS(a, v) memset(a, v, sizeof(a))
 #define  debug( a )  cout << #a << " = "  << a <<endl
 #define  abs(x) x<0?-x:x
 #define  srd(a) scanf("%d", &a)
 #define  src(a) scanf("%c", &a)
 #define  srs(a) scanf("%s", a)
 #define  srdd(a, b) scanf("%d %d",&a, &b)
 #define  srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
 #define  prd(a) printf("%d\n", a)
 #define  prdd(a, b) printf("%d %d\n",a, b)
 using   namespace   std;
typedef   long   long   ll;
  const   int  maxn =  1005  ;
  int   n, m, num, T, k, x, y, len, ans;
  int   Map[maxn][maxn];
  bool   vis[maxn];
  int   link[maxn];

  bool  dfs( int   x) {
      for ( int  j= 0 ; j<n; j++ ) {
          if ( Map[x][j] && ! vis[j] ) {
            vis[j]  =  true  ;
              if ( link[j]==- 1  ||  dfs(link[j]) ) {
                link[j]  =  x;
                  return   true  ;
            }
        }
    }
      return   false  ;
} 

  void   solve() {
      int  res =  0  ;
    CLS(link,  - 1  );
      for ( int  i= 0 ; i<n; i++ ) {
        CLS(vis,   false  );
          if ( dfs(i) ) res ++ ;
    }
    prd(n -res/ 2  );
}

  void   input() {
      while ( ~ srd(n) ) {
        memset(Map,   0 ,  sizeof  (Map));
          for ( int  i= 0 ; i<n; i++ ) {
            scanf(  "  %d: (%d)  " , &x, & num);
              for ( int  j= 0 ; j<num; j++ ) {
                srd(y);
                Map[x][y]  =  1  ;
            }
        }
        solve();
    }
}

  int   main(){
    input();
      return   0  ;
} 

再贴一个题。。 http://acm.hdu.edu.cn/showproblem.php?pid=1054

但是，很尴尬的是，我不用vector竟然时间超限。。蒙~~~

求最小顶点覆盖。由于本题是双向图，所以最小顶点覆盖等于双向图的最大匹配/2 。

 //  Asimple
 #include <bits/stdc++.h>
 #define  INF 0xffffff
 #define  mod 1000000
 #define  swap(a, b, t) t = a, a = b, b = t
 #define  CLS(a, v) memset(a, v, sizeof(a))
 #define  debug( a )  cout << #a << " = "  << a <<endl
 #define  abs(x) x<0?-x:x
 #define  srd(a) scanf("%d", &a)
 #define  src(a) scanf("%c", &a)
 #define  srs(a) scanf("%s", a)
 #define  srdd(a, b) scanf("%d %d",&a, &b)
 #define  srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
 #define  prd(a) printf("%d\n", a)
 #define  prdd(a, b) printf("%d %d\n",a, b)
 using   namespace   std;
typedef   long   long   ll;
  const   int  maxn =  1505  ; 
 int   n, m, num, T, k, x, y, len, ans;
  int   endx, endy, t; 
 bool   vis[maxn];
  int   link[maxn]; 
vector< int >  Map[maxn];

  bool  dfs( int   x) {
      int   l ;
      for ( int  j= 0 ; j<Map[x].size(); j++ ) {
        l  =  Map[x][j];
          if ( ! vis[l] ) {
            vis[l]  =  true  ;
              if ( link[l]==- 1  ||  dfs(link[l]) ) {
                link[l]  =  x;
                  return   true  ;
            }
        }
    }
      return   false  ;
} 

  void   solve() {
      int  res =  0  ;
    CLS(link,  - 1  );
      for ( int  i= 0 ; i<n; i++ ) {
        CLS(vis,   false  );
          if ( dfs(i) ) res ++ ;
    }
    prd(res / 2  );
}

  void   input() {
      while ( ~ srd(n) ) {
          for ( int  i= 0 ; i<n; i++ ) Map[i].clear();
          for ( int  i= 0 ; i<n; i++ ) {
            scanf(  "  %d: (%d)  " , &x, & num);
              for ( int  j= 0 ; j<num; j++ ) {
                srd(y);
                Map[x].push_back(y);
                Map[y].push_back(x);
  //                  Map[x][y] = 1;
  //                  Map[y][x] = 1; 
             }
        }
        solve();
    }
}

  int   main(){
    input();
      return   0  ;
} 

 最后一道~ http://acm.hdu.edu.cn/showproblem.php?pid=1151

最小路径覆盖数，双向图，所以res/2。

 //  Asimple
 #include <bits/stdc++.h>
 #define  INF 0xffffff
 #define  mod 1000000
 #define  swap(a, b, t) t = a, a = b, b = t
 #define  CLS(a, v) memset(a, v, sizeof(a))
 #define  debug( a )  cout << #a << " = "  << a <<endl
 #define  abs(x) x<0?-x:x
 #define  srd(a) scanf("%d", &a)
 #define  src(a) scanf("%c", &a)
 #define  srs(a) scanf("%s", a)
 #define  srdd(a, b) scanf("%d %d",&a, &b)
 #define  srddd(a, b, c) scanf("%d %d %d",&a, &b, &c)
 #define  prd(a) printf("%d\n", a)
 #define  prdd(a, b) printf("%d %d\n",a, b)
 using   namespace   std;
typedef   long   long   ll;
  const   int  maxn =  1005  ; 
 int   n, m, num, T, k, x, y, len, ans;
  int   endx, endy, t; 
 int   Map[maxn][maxn]; 
 bool   vis[maxn];
  int   link[maxn]; 

 bool  dfs( int   x) {
      for ( int  j= 1 ; j<=n; j++ ) {
          if ( Map[x][j] && ! vis[j] ) {
            vis[j]  =  true  ;
              if ( link[j]==- 1  ||  dfs(link[j]) ) {
                link[j]  =  x;
                  return   true  ;
            }
        }
    }
      return   false  ;
} 

  void   solve() {
      int  res =  0  ;
    CLS(link,  - 1  );
      for ( int  i= 1 ; i<=n; i++ ) {
        CLS(vis,   false  );
          if ( dfs(i) ) res ++ ;
    }
    prd(n - res);
}

  void   input() {
    srd(T);
      while ( T --  ) { 
         srdd(n, num);
        memset(Map,   0 ,  sizeof  (Map));
          for ( int  i= 0 ; i<num; i++ ) {
            srdd(x, y);
            Map[x][y]  =  1  ; 
         }
        solve();
    }
}

  int   main(){
    input();
      return   0  ;
} 

 

查看更多关于图论相关之匈牙利算法的详细内容...