巢穴

about:blank

P3041

2分图/匈牙利
第一遍写疵了..
#include <iostream>
#include <fstream>
using namespace std;


const int MAXN=501;
int n,k;
bool edge[MAXN][MAXN];
bool hash[MAXN];
int v[MAXN];
bool find(int x)
{

     for (int j=1;j<=n;j++)
     {
      if  (!edge[x][j]) continue;
      if (!hash[j])
      {
       hash[j]=true;
       if (v[j]==0||find(v[j]))
       {
        v[j]=x;
        return true;
       }
      }
     }
     return false;
}
int main()
{
    memset(edge,0,sizeof(edge));
    

    cin>>n>>k;
    
    for (int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        edge[x][y]=true;
    }
    int count=0;
    for (int i=1;i<=n;i++)
    {
        memset(hash,0,sizeof(hash));
        if (find(i)) count++; 
    }
    cout<<count<<endl;
  // system("pause");
    return 0;
}

posted on 2009-10-07 19:21 Vincent 阅读(77) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理