pku1087.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#include <map>
#include <string>
#define size 160
using namespace std;

map < string, int > ID;
int G[size * 2][size * 2];
int path[size][size];
int S[size];
int T[size];
int v[size];
int match[size];
int N, M, K, L;

int GetID(char s[])
{
	if (ID.find(s) != ID.end())
	{
		return ID[s];
	}
	else
	{
		return ID[s] = L++;
	}
}

int DFS(int p)
{
	int i, t;
	for (i = 0; i < M; i++)
	{
		if (!v[i] && path[p][i])
		{
			v[i] = 1;
			t = match[i];
			match[i] = p;
			if (t == -1 || DFS(t))
				return 1;
			match[i] = t;
		}
	}
	return 0;
}

int main()
{
	char sa[30], sb[30];
	int ida, idb;
	int i, j, k;
	int cnt;
	scanf("%d", &N);
	L = 0;
	for (i = 0; i < N; i++)
	{
		scanf("%s", sa);
		S[i] = GetID(sa);
	}
	scanf("%d", &M);
	for (i = 0; i < M; i++)
	{
		scanf("%s %s", sa, sa);
		T[i] = GetID(sa);
	}
	memset(G, 0, sizeof(G));
	for (i = 0; i < size * 2; i++)
	{
		G[i][i] = 1;
	}
	scanf("%d", &K);
	while (K--)
	{
		scanf("%s %s", sa, sb);
		ida = GetID(sa);
		idb = GetID(sb);
		G[idb][ida] = 1;
	}
	for (k = 0; k < L; k++)
	{
		for (i = 0; i < L; i++)
		{
			for (j = 0; j < L; j++)
			{
				if (G[i][k] && G[k][j])
				{
					G[i][j] = 1;
				}
			}
		}
	}
	memset(path, 0, sizeof(path));
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			path[i][j] = G[S[i]][T[j]];
		}
	}
	memset(match, -1, sizeof(match));
	cnt = 0;
	for (i = 0; i < N; i++)
	{
		memset(v, 0, sizeof(v));
		if (DFS(i))
			cnt++;
	}
	printf("%d\n", M - cnt);
	return 0;
}