1197唯一完全匹配.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<string.h>
int graph[100][100];
int cover[100];
int link[100];
int slink[100];
int wa[100];
int T,n;
bool findx(int t)
{
	int i;
	int q;
	for(i=1;i<=n;i++)if(cover[i]==0&& graph[t][i]==1)
	{
		cover[i]=1;q=link[i];link[i]=t;
		if(q==0 || findx(q))return true;
		link[i]=q;
	}
	return false;
}


int main()
{
	int i,j,k,l;
	int p[100][5];
	int q[100][3];
	
	
	T=0;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)break;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d%d",&p[i][1],&p[i][2],&p[i][3],&p[i][4]);
			p[i][0]=0;
		}
		
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&q[i][1],&q[i][2]);
			q[i][0]=0;
		}
		T++;
		int flag=1;
		int cnt=0;
		memset(graph,0,sizeof(graph));
		for( i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
	
					if(q[i][1]>p[j][1] && q[i][1]<p[j][2] && q[i][2]>p[j][3] && q[i][2]<p[j][4])
					{
						graph[i][j]=1;
					}
			}
		memset(link,0,sizeof(link));
		for(i=1;i<=n;i++)
		{
			memset(cover,0,sizeof(cover));
			if(findx(i))cnt++;
		}
		memset(wa,0,sizeof(wa));
		memcpy(slink,link,sizeof(link));
		for(j=1;j<=n;j++)
		{
			graph[slink[j]][j]=0;
			memset(link,0,sizeof(link));
			cnt=0;
			for(i=1;i<=n;i++)
			{
				memset(cover,0,sizeof(cover));
				if(findx(i))cnt++;
			}
			if(cnt!=n-1 || slink[j]==0)wa[j]=1;
			graph[slink[j]][j]=1;
		}






		
		printf("Heap %d\n",T);
		int fir=1;
		for(i=1;i<=n;i++)
		{
			if(wa[i]==0)
			{
				if(fir!=1)printf(" ");
				printf("(%c,%d)",char(64+i),slink[i]);
				fir=0;
			}
		}
		if(fir==1)printf("none");
		printf("\n");
		printf("\n");

	}
	return 0;
}