USACO 4.2.2 The Perfect Stall 完美的牛欄 stall4

本文正體字版由OpenCC轉換

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

/*
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;
}

上次修改時間 2017-02-03

相關日誌