POJ 3041 C++ （图论）

//最近专用Ford_Fulkerson 和hungary水到手软
//最小割定理是一个二分图中很重要的定理－－－一个二分图中的最大匹配数等于这个图中的最小点覆盖数。
//最小点覆盖：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边
#include<iostream>
using namespace std;
int n,m,res;
int l[500],r[500],map[500][500],used[500];
bool path(int u)
{int v;
for(v=0;v<n;v++)
     if(map[u][v] && !used[v])
       {used[v]=1;
        if(r[v]==-1 || path(r[v]))
           {  l[u]=v;
              r[v]=u;
              return true;
           }
       }
   return false;        
}
void solve()
{ int i;
  memset(l,-1,sizeof(l));
  memset(r,-1,sizeof(r));
  for(i=0;i<n;i++)
       if(l[i]==-1)
           {  memset(used,0,sizeof(used));
              if(path(i))
                  res++;
           }  

}
int main()
{ int i,a,b;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while((scanf("%d%d",&n,&m))!=EOF)
       { memset(map,0,sizeof(map));
         for(i=0;i<m;i++)
             { scanf("%d%d",&a,&b);
               map[a-1][b-1]=1;
              }
           res=0; 
           solve();
           cout<<res<<endl;            
         }
   return 0;      
}              

posted on 2008-11-29 15:37 蜗牛 阅读(888) 评论(0)  编辑 收藏 引用 所属分类: ACM ICPC