hungary.cpp

来自「给定一个（无向）图G」· C++ 代码 · 共 48 行

/* Problem "unique" */

#include <fstream>
using namespace std;

ifstream fin("data.in");
ofstream fout("result.out");

int n,m;
bool connect[201][201]={0};
bool used[201]={0};
int link[201]={0};

void init(){
    fin>>n>>m;
    int p;
    for(int i=1;i<=n;i++)
        do{
            fin>>p;
            if(p) connect[i][p]=true;
            else break;
        }while(1);
}

bool check(int t){
    for(int i=1;i<=m;i++)
        if(!used[i] && connect[t][i]){
            used[i]=true;
            if(!link[i] || check(link[i])){
                link[i]=t;
                return true;
            }
        }
    return false;
}

int main(){
    init();
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(used,0,sizeof(used));
        if(check(i)) ans++;
    }
    fout<<ans<<endl;
}

/* Program by Fengzee, 2008.2.3 */