首页 > 代码库 > 【匈牙利算法】 二分图模板 poj 1274

【匈牙利算法】 二分图模板 poj 1274

#include <iostream>#include <cstdio>#include <memory.h>using namespace std;int n,m,num,temp,sum;int re[201][201],link[201];//牛与牛栏的对应关系bool tag[201];//增益路径bool DFS(int a){    for(int i=1;i<=m;i++)    {        if(re[a][i]!=0 && !tag[i])//如果节点i与a相邻并且未被查找过        {            tag[i]=true;//标记i为已查找过            if(link[i]==-1||DFS(link[i]))//i在匹配M中,但是从与i相邻的节点出发可以有增广路            {                link[i]=a;//记录查找成功记录//                cout << "sucess i=" << i << "   link[i]= "<<link[i] <<endl;                return true;//返回查找成功            }        }    }    return false;}int main(){    //freopen("in.txt","r",stdin);    while(cin>>n>>m) // cow stall    {        int i,j,sum=0;        memset(re,0,sizeof(re));        memset(link,-1,sizeof(link));        for(i=1;i<=n;i++)        {            cin>>num;            for(j=1;j<=num;j++)            {                cin>>temp;                re[i][temp]=1;            }        }//初始化        for(i=1;i<=n;i++)   //cow        {            for(j=1;j<=m;j++)   //stall            {                tag[j]=false;            }            if(DFS(i))//从节点i尝试扩展            sum++;        }        cout << sum << endl;    }    return 0;}

 

【匈牙利算法】 二分图模板 poj 1274