简单二分图匹配-白红宇

简单二分图匹配

阅读量：4616 次

发布时间：2019-06-09

本文共 3021 字，大约阅读时间需要 10 分钟。

1.HDU 2063 过山车

模板题。。

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; int color[1100]; int match[1100]; int mp[1100][1100]; int leftnum, rightnum; void init( ) { for( int i = 1; i <= 1000; i++) { color[i] = 0; match[i] = -1; } for( int i = 1; i <= 1000; i++) { for( int j = 1; j <= 1000; j++) mp[i][j] = 0; } } int find( int x) { for( int i = 1; i <= rightnum; i++) { if (!color[i] && mp[x][i]) { color[i] = 1; if (match[i] == -1 || find(match[i])) { match[i] = x; return 1; } } } return 0; } int solve( ) { int cnt = 0; for( int i = 1; i <= leftnum; i++) { memset(color, 0, sizeof(color)); if ( find(i) ) cnt++; } return cnt; } int main( ) { int k, M, N, a, b; while ( scanf("%d", &k), k) { scanf("%d%d", &M, &N); init( ); leftnum = rightnum = 0; for( int i = 1; i <= k; i++) { scanf("%d%d", &a, &b); mp[a][b] = 1; if (a > leftnum ) leftnum = a; if (b > rightnum ) rightnum = b; } printf("%d\n", solve( )); } return 0; }

2.HDU 2444

要判断能不能构成二分图。。构好图。

然后就直接用匈牙利算法就可以了

View Code

#include 
      
        #include 
       
         #include 
        
          int left[1000], right[1000], ld, rd; int mp[300][300]; int match[300]; int color[300]; void init( ) {
      memset(left, 0, sizeof(left));   memset(right, 0, sizeof(right));   memset(match, -1, sizeof(match));   memset(mp, 0, sizeof(mp));   ld = 0, rd = 0; } int find( int x ) {
    for( int j = 1; j < rd; j++)   {
    int i = right[j]; //printf("color = %d mp = %d\n",mp[x][i], color[i]);     if( mp[x][i] && !color[i] )     {
          color[i] = 1; //puts("A");       if( match[i] == -1 || find(match[i]))       {
             match[i] = x; return 1;       }     }   } return 0; } void solve(  ) {
    int cnt = 0; for( int j = 1; j < ld; j++)   {
    int i = left[j];      memset(color, 0, sizeof(color)); if( find(i) )         cnt++;   }   printf("%d\n", cnt); } int main( ) {
    int N, M, a, b; while( scanf("%d%d",&N, &M) != EOF )    {
         init( ); int x = 0; for( int i = 1; i <= M; i++)      {
            scanf("%d%d",&a,&b);         mp[a][b] = mp[b][a] = 1; int f1 = 0, f2 = 0; if( !left[a] && !right[a])             left[a] = 1, f1 = 1, ld++; if( !left[a] && !right[b] && !f1)             left[b] = 1, f2 = 1, ld++; if( !left[a] && !right[a] && !f1)             right[a] = 1, rd++; if( !left[b] && !right[b] && !f2)             right[b] = 1, rd++; if( (left[a] && left[b]) || (right[a] && right[b] ))               x = 1;      } // printf("%d \n", x);      if( x == 1 || ld == N || rd == N )      {
            puts("No"); continue;      }      ld = rd = 1; //X集合       for( int i = 1; i <= N; i++) if( left[i] )         left[ld++] = i; //Y集合      for( int i = 1; i <= N; i++) if( right[i] )         right[rd++] = i;      solve( );    } }