最大照合担当者割当

最大マッチング人員配分Time Limit:1000 MS Memory Limit:65536 K Total Submit:158 Accepted:83 DescriptionにはM人の労働者x 1,x 2,...,xm,...,N人の労働者y 1,y 2,...,ynが設置されており、各労働者は最大1つの仕事をし、各仕事は最大1人の労働者を割り当てることになっている.いろいろな原因で、労働者一人一人がその中の1つまたはいくつかの仕事に適任するしかない.どのように分配すればできるだけ多くの労働者を彼の適任な仕事に分配することができるかを聞く.この問題を人員配分問題と呼ぶ.Inputの第1行の2つの整数m,nはそれぞれ労働者数と作業数である.次の整数sは、二分図の辺数です.次のs行は、行ごとに2つのaiを数え、biはai番目の労働者がbi番目の仕事に適任できるという整数を表し、最大何人の労働者を自分の適任な仕事に派遣できるかを示しています.Sample Input

3 3
4
1 2
2 1
3 3
1 3

Sample Output

3

Hint規模:1<=m,n<=100 1<=s<=10000 Source cwjテンプレート不解釈

#include
#include
#include
#include
#include

using namespace std;

struct node
{
	int to,next;
}a[10001];

int tot,n,m,p,f[10001],head[10001],vis[10001],ans,link[10100];

int find(int x)
{
	for (int i=head[x];i;i=a[i].next)
	{
		int j=a[i].to;
		if (!f[i])
		{
			int q=link[j];
			link[j]=x;
			f[i]=1;
			if (!q||find(q)) return 1;
			link[j]=q;
		}
	}
	return 0;
}

int main()
{
	cin>>n>>m;
	cin>>m; 
	for (int i=1;i<=m;i++)
	{
		int dd,ddd;
		cin>>dd>>ddd;
		a[++tot].next=head[dd];
		a[tot].to=ddd;
		head[dd]=tot;
	}
	for (int i=1;i<=n;i++)
	{
		memset(f,0,sizeof(f));
		ans+=find(i);
	}
	cout<

[Submit]   [Go Back]   [Status]   [Discuss]
Home Page   Go Back  To top