匈牙利算法

 2009-03-30 17:42

#include<iostream>
#include<fstream>
using namespace std;

const int MAX = 100;

struct{
      int n;
      int adjvex[MAX];
}Edge[MAX];

int xn,n;

bool vs[MAX];
int Match[MAX];

int Hungary();

int main(void){
    int e,a,b;
    int i,j;
    ifstream in("data.in");
    ofstream out("data.out");
   
    in>>xn>>n>>e;
    for(i=0;i<=n+1;i++)
        Edge[i].n = 0;
   
    for(i=0;i<e;i++){
        in>>a>>b;
        Edge[a].adjvex[ Edge[a].n++ ] = b;
    }
   
    out<<Hungary()<<endl;
    for(i=xn+1;i<=n;i++)
        out<<"Match["<<i<<"]="<<Match[i]<<endl;
   
    system("pause");
    return 0;
}

bool Add(int cur){
     int i,j,u,v;
    
     for(i=0;i<Edge[cur].n;i++){
         u = Edge[cur].adjvex[i];
         if(!vs[u]){
            vs[u] = true;
            if(Match[u]==0){
               Match[u] = cur;
               return true;
            }
            else if(Add(Match[u]) ){
                 Match[u] = cur;
                 return true;
            }
         }
     }
    
     return false;
}

int Hungary(){
    int i,r;
   
    memset(Match,0,sizeof(Match) );
    r = 0;
    for(i=1;i<=xn;i++){
        memset(vs,0,sizeof(vs) );
        if(Add(i) ) r++;
    }
   
    return r;
}