USACO 4.2.2 The Perfect Stall 完美的牛欄 stall4

最簡單的求二分圖最大匹配,最樸素的匈牙利算法解決。

/*
ID: cmykrgb1
PROG: stall4
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 402
#define PV 200
using namespace std;
ifstream fi("stall4.in");
ofstream fo("stall4.out");
int N,M,mat;
int adjl[MAX][MAX];
int match[MAX];
bool onpath[MAX];

void init()
{
    int i,j,a,b;
    fi >> N >> M;
    for (i=1;i<=N;i++)
    {
        fi >> a;
        for (j=1;j<=a;j++)
        {
            fi >> b;
            adjl[i][ ++adjl[i][0] ]=b+PV;
            adjl[b+PV][ ++adjl[b+PV][0] ]=i;
        }
    }
}

bool cross(int i)
{
    int k,j;
    for (k=1;k<=adjl[i][0];k++)
    {
        j=adjl[i][k];
        if (!onpath[j])
        {
            onpath[j]=true;
            if (!match[j] || cross(match[j]))
            {
                match[j]=i;
                return true;
            }
        }
    }
    return false;
}

void hungary()
{
    int i;
    for (i=1;i<=N;i++)
    {
        if (cross(i))
            mat++;
        memset(onpath,0,sizeof(onpath));
    }
}

void print()
{
    fo << mat << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    hungary();
    print();
    return 0;
}

相關日誌