Codeforces ラウンド #277.5 (ディビジョン 2)B??BerSU Ball_html/css_WEB-ITnose

B. BerSU Ball

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

The Berland州立大学は創立 100500 周年を記念して社交ダンスを主催しています。 N 人の男の子と M 人の女の子は、すでにワルツ、メヌエット、ポロネーズ、カドリーユの動きのリハーサルで忙しいです。

私たちは、数組の男の子と女の子のペアが舞踏会に招待されることを知っています。ただし、各ペアのパートナーのダンス スキルの差は最大でも 1 つでなければなりません。

各少年のダンス スキルはわかっています。同様に、私たちは各女の子のダンススキルを把握しています。 n 人の男の子と m 人の女の子から形成できるペアの最大数を決定できるコードを作成します。

入力

最初の行には整数 n (1?≤?n?≤?100) が含まれます。男の子の数。 2 行目にはシーケンス a1,?a2,?...,?an (1?≤?ai?≤?100) が含まれています。ここで、ai は i 番目の少年のダンス スキルです。

同様に、3 行目には整数が含まれています。 m (1?≤?m?≤?100) ?女の子の数。 4 行目にはシーケンス b1,?b2,?...,?bm (1?≤?bj?≤?100) が含まれます。ここで、bj は j 番目の女の子のダンス スキルです。

出力

単一の出力番号 ？必要なペアの最大可能数。

サンプルテスト

入力

41 4 6 255 1 5 7 9

出力

入力

41 2 3 4410 11 12 13

出力

入力

51 1 1 1 131 2 3

出力

二分適合模板题

#include <map>#include <set>#include <list>#include <queue>#include <stack>#include <vector>#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 110;int mark[N];bool vis[N];int head[N];int tot;int n, m;int b[N];int g[N];struct node{	int next;	int to;}edge[N * N];void addedge(int from, int to){	edge[tot].to = to;	edge[tot].next = head[from];	head[from] = tot++;}bool dfs(int u){	for (int i = head[u]; ~i; i = edge[i].next)	{		int v = edge[i].to;		if (!vis[v])		{			vis[v] = 1;			if (mark[v] == -1 || dfs(mark[v]))			{				mark[v] = u;				return 1;			}		}	}	return 0;}int hungry(){	memset(mark, -1, sizeof(mark));	int ans = 0;	for (int i = 1; i <= n; ++i)	{		memset(vis, 0, sizeof(vis));		if (dfs(i))		{			ans++;		}	}	return ans;}int main(){	while (~scanf("%d", &n))	{		for (int i = 1; i <= n; ++i)		{			scanf("%d", &b[i]);		}		scanf("%d", &m);		for (int i = 1; i <= m; ++i)		{			scanf("%d", &g[i]);		}		memset (head, -1, sizeof(head));		tot = 0;		for (int i = 1; i <= n; ++i)		{			for (int j = 1; j <= m; ++j)			{				if(abs(b[i] - g[j]) <= 1)				{					addedge(i, j);				}			}		}		printf("%d\n", hungry());	}	return 0;}