1087.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"string.h"

#define null 0
const int size=1000;
bool w[size][size];

void maxmatch(int n,int m,int *p)
{
	int p_n[size];
	int p_m[size];
	bool sign[size];
	int q[size],from[size],s,t;

	int i,j,link,now,h;
	

	for(i=0;i<n;i++)p_n[i]=-1;
	for(j=0;j<m;j++)p_m[j]=-1;

	for(i=0;i<n;i++)
	if(p_n[i]==-1)
	{
	
		for(j=0;j<m;j++)sign[j]=0;
				
		s=0;
		
		for(j=0;j<m;j++)
			if(w[i][j]!=null)
			{
				q[s]=j;
				from[s++]=-1;
				sign[j]=1;
			}

		for(t=0;t<s;t++)
		{
			now=q[t];
			if(p_m[now]==-1)
			{
				link=t;
				break;
			}
			else
			{
				for(j=0;j<m;j++)
				if(w[p_m[now]][j]!=null&&sign[j]==0)
				{
					sign[j]=1;
					q[s]=j;
					from[s++]=t;
				}
			}
		}

		if(t<s)
		{
			while(from[link]!=-1)
			{
				h=from[link];
				p_m[q[link]]=p_m[q[h]];
				
				p_n[p_m[q[h]]]=q[link];
				link=h;
			}
			
			p_m[q[link]]=i;
			p_n[i]=q[link];
		}

	}

	for(i=0;i<n;i++)p[i]=p_n[i];
	
	return ;
}

int main()
{
	bool map[501][501];
	char name[501][30],w1[30],w2[30];
	char device[501][30];
	int n,m,e,i,j,a,b,k,an[510],tn;

	cin>>n;
	tn=n;

	for(i=0;i<n;i++)
		cin>>name[i];

	cin>>m;
	for(i=0;i<m;i++)
	{
		cin>>w1>>device[i];
		for(a=0;a<n;a++)
		if(strcmp(device[i],name[a])==0)break;

		if(a==n)strcpy(name[n++],device[i]);
	}

	cin>>e;

	for(i=0;i<501;i++)
	for(j=0;j<501;j++)
		if(i!=j)map[i][j]=0;
		else map[i][j]=1;


	for(i=0;i<e;i++)
	{
		cin>>w1;
		cin>>w2;

		for(a=0;a<n;a++)
		if(strcmp(w1,name[a])==0)break;
		
		if(a==n)strcpy(name[n++],w1);

		for(b=0;b<n;b++)
		if(strcmp(w2,name[b])==0)break;
		
		if(b==n)strcpy(name[n++],w2);

		//if(a<n&&b<n)
		map[a][b]=1;
	}
	

	
	for(k=0;k<n;k++)
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
		map[i][j]|=map[i][k]&&map[k][j];
	
	for(i=0;i<m;i++)
	for(j=0;j<n;j++)
		w[i][j]=0;
		
	for(i=0;i<m;i++)
	{
		for(a=0;a<n;a++)
		if(strcmp(device[i],name[a])==0)break;

		for(j=0;j<tn;j++)w[i][j]=map[a][j];
	}

	maxmatch(m,tn,an);
	int answer;

	for(i=0,answer=0;i<m;i++)
		if(an[i]<0)answer++;
	
		cout<<answer<<endl;

	return 0;
}