POJ 3041 C++ （圖論）

//最近專用Ford_Fulkerson 和hungary水到手軟
//最小割定理是一個(gè)二分圖中很重要的定理－－－一個(gè)二分圖中的最大匹配數(shù)等于這個(gè)圖中的最小點(diǎn)覆蓋數(shù)。
//最小點(diǎn)覆蓋：假如選了一個(gè)點(diǎn)就相當(dāng)于覆蓋了以它為端點(diǎn)的所有邊，你需要選擇最少的點(diǎn)來(lái)覆蓋所有的邊
#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 蝸牛 閱讀(838) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM ICPC