#include<stdio.h>
#include<string.h>
#define maxn 2800
#define maxL 50
int n,m,k;
char recept[maxn][maxL],lr;
char need[maxn][maxL];
int g[maxn][maxn];
int check[maxn],cov[maxn];
int fromto[maxn][maxn];
int i1,i2;
char s1[maxL],s2[maxL];

void add()
{
	int i;
	for(i=1;i<=lr;i++)
		if(strcmp(recept[i],s1)==0)
			break;
	if(i>lr)
	{
		lr++;
		strcpy(recept[lr],s1);
		i1=lr;
	}
	else
		i1=i;

	for(i=1;i<=lr;i++)
		if(strcmp(recept[i],s2)==0)
			break;
	if(i>lr)
	{
		lr++;
		strcpy(recept[lr],s2);
		i2=lr;
	}
	else
		i2=i;
}
int dfs(int a)
{
	for(int i=1;i<=n;i++)
	{
		if(g[a][i]==1 && !check[i])
		{
			check[i]=1;
			if(cov[i]==0||dfs(cov[i]))
			{
				cov[i]=a;
				return 1;
			}
		}
	}
	return 0;
}
int max_match()
{
	int i;
	int ans=0;
	for(i=1;i<=n;i++){
		memset(check,0,sizeof(check));
		if(dfs(i))
			ans++;
	}
	return ans;
}
int main()
{
	//freopen("f.in","r",stdin);
	int i,j,t;
	
	memset(g,0,sizeof(g));
	memset(cov,0,sizeof(cov));
	memset(fromto,0,sizeof(fromto));

	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%s",recept[i]);
	lr=n;
	scanf("%d",&m);
	for(i=1;i<=m;i++)
		scanf("%s %s",s1,need[i]);
	scanf("%d",&k);
	for(i=0;i<k;i++){
		scanf("%s %s",s2,s1);
		i1=i2=1;
		add();
		fromto[i1][i2]=1;
	}
	for(i=1;i<=lr;i++)
		fromto[i][i]=1;
	for(t=1;t<=lr;t++)
		for(i=1;i<=lr;i++)
			for(j=1;j<=lr;j++)
				fromto[i][j]=fromto[i][j]||fromto[i][t]&&fromto[t][j];
	for(i=1;i<=n;i++)
		for(j=1;j<=lr;j++)
			if(fromto[i][j])
				for(t=1;t<=m;t++)
					if(strcmp(recept[j],need[t])==0)
						g[i][t]=1;
	printf("%d\n",m-max_match());

	return 0;
}

• Re:sorry，搞错个变量，变成ＷＡ了，自己解决。。。 (1903) HeartRush 2007-09-12 13:31:56