2199484_wa.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <string.h>

int n, d, k, no;
char plug[502][30];
char dev[502][30];
int g[502][502];
int b[502], link[502];
char tmp1[30], tmp2[30], tmp[30], adp[502][30];

void warshall(int map[][502])
{
	int i, j, m;

	for(i = 0; i < no; i++)
	{
		for(j = 0; j < no; j++)
			if(map[j][i])
				for(m = 0; m < no; m++)
					map[j][m] += map[i][m];
	}
}

void insert(int i,int j)
{
	int m, p;

	for(m = 1; m <= n; m++)
		if(strcmp(plug[m],adp[j])==0)
			for(p = 1; p <= d; p++)
				if(strcmp(adp[i],dev[p])==0)
					g[m][p] = 1;
}

int find(int a)
{
	int i;

	for(i = 1; i <= d; i++)
	{
		if(g[a][i]&&!b[i])
		{
			b[i] = 1;
			if(!link[i]||find(link[i]))
			{
				link[i] = 1;
				return 1;
			}
		}
	}
	return 0;
}

void solve(int map[][502])
{
	int i, j, ans;

	ans = 0;
	for(i = 0; i < no; i++)
		for(j = 0; j < no; j++)
			if(map[i][j])
				insert(i,j);
	for(i = 1; i <= n; i++)
	{
		memset(b,0,sizeof(b));
		if(find(i))
			ans++;
	}
	printf("%d\n",d-ans);
}

void input()
{
	int f1, f2;
	int i, j, m;
	int map[502][502];
	
	scanf("%d",&n);
	no = 0;
	memset(map,0,sizeof(map));
	memset(g,0,sizeof(g));
	for(i = 1; i <= n; i++)
		scanf("%s",plug[i]);
	scanf("%d",&d);
	for(i = 1; i <= d; i++)
	{
		scanf("%s%s",tmp,dev[i]);
		for(j = n; j > 0; j--)
			if(strcmp(dev[i],plug[j])==0)
				g[j][i] = 1;
	}
	scanf("%d",&k);
	for(i = 1; i <= k; i++)
	{
		scanf("%s%s",tmp1,tmp2);
		if(strcmp(tmp2,tmp1)==0)
			continue;
		f1 = f2 = 0;
		for(j = 0; j <no; j++)
			if(strcmp(tmp1,adp[j])==0)
			{
				f1 = 1;
				break;
			}
		for(m = 0; m < no; m++)
			if(strcmp(tmp2,adp[m])==0)
			{
				f2 = 1;
				break;
			}
		if(f1)
		{
			if(f2)
				map[j][m] = 1;
			else
			{
				strcpy(adp[no],tmp2);
				map[j][no++] = 1;
			}
		}
		else
		{
			if(f2)
			{
				strcpy(adp[no],tmp1);
				map[no++][m] = 1;
			}
			else
			{
				strcpy(adp[no++],tmp1);
				strcpy(adp[no++],tmp2);
				map[no-2][no-1] =1;
			}
		}
	}
	warshall(map);
	solve(map);
}

int main()
{
	input();
	return 1;
}