1027wedding.txt

来自「厦门大学ACM题库中的1027婚礼问题」· 文本 代码 · 共 187 行

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAXV 30
//边结点结构类型
typedef struct ANode{
	int sexnum;//该边的亲密人
	struct ANode* nextarc;
}ArcNode;
//邻接表头结点类型
typedef struct VNode{
	ArcNode *firstarc;
}VNode;
typedef VNode AdjList[MAXV];
typedef struct{
	AdjList adjlist;//邻接表
}AGraph;
AGraph* Husband,*Wife;
int Brideline[MAXV];
int Groomline[MAXV];
int mark;   
int flag; 
int tag; 
//2h以20形式存入，2w以21形式存入
void Back_Bride(int i,int n)
{
    int j,a;  
	ArcNode* p;
	tag=1;
    if(mark!=1 && flag!=1)   
    {   
        if(i==n)   
        {   
            flag=1;   
            for(j=1;j<n;j++)   
            {   
				a=Brideline[j]%10;
				if(a==0)printf("%dh ",j);
				else printf("%dw ",j); 
            }  
			//printf("\n");
            return;   
        } 
        if(Husband->adjlist[i].firstarc!=NULL)
		{
			j=1; 
			while(j<=i-1)
			{
				for(p=Husband->adjlist[i].firstarc;p!=NULL;p=p->nextarc)
				{
					if(p->sexnum==Groomline[j])
					{
		     			tag=0;break;//tag用来标记前面i-1人中与第i个人有亲密关系的，有则不可放
					}
					
				}
				if(!tag)break;
				else j++;
			}
		}
		if(tag)//如果可以放的话
		{
			Groomline[i]=i*10;//放i号husband
			Brideline[i]=i*10+1;//放i号wife
			Back_Bride(i+1,n);//回溯
		}
		if(!tag && !mark)//Groomline[i]不可以放i号husband时,看放i号wife行不行
		{
			tag=1;//恢复tag=1;
			if(Wife->adjlist[i].firstarc!=NULL)//需要作判断时
			{
				j=1; 
				while(j<=i-1)
				{
					for(p=Wife->adjlist[i].firstarc;p!=NULL;p=p->nextarc)
					{
						if(p->sexnum==Groomline[j])
							tag=0;
						break;
					}
					
					if(!tag)break;
					else j++;
				}
			}
			if(tag)//如果放第i号wife可以的话
			{
				Groomline[i]=i*10+1;
				Brideline[i]=i*10;
				Back_Bride(i+1,n);
			}
			else{//如果放第i号wife不可以的话
				mark=1;   
				printf("bad luck\n");   
				return;   
			}
		}
		else 
			return;
	}
}	
int main()
{
	int n,m,i,j,c,num,a,tum;
		ArcNode* p;
		int first=1;
		char string1[2],string2[2];
		scanf("%d%d",&n,&m);
	while(first==1)
	{
		    flag=0;
		    mark=0;
			Husband=(AGraph*)malloc(sizeof(AGraph));
			Wife=(AGraph*)malloc(sizeof(AGraph));
			for(i=1;i<n;i++)
			{
				Husband->adjlist[i].firstarc=NULL;
				Wife->adjlist[i].firstarc=NULL;
				Brideline[i]=0;
				Groomline[i]=0;
			}
			for(j=1;j<=m;j++)
			{
				scanf("%s%s",string1,string2);
				a=string1[0]-'0';
				if(string1[1]=='h')
				{
					c=string2[0]-'0';
					if(string2[1]=='h')
					{
						num=c*10;
						tum=a*10;	
						p=(ArcNode*)malloc(sizeof(ArcNode));
						p->sexnum=tum;
						p->nextarc=Husband->adjlist[c].firstarc;
						Husband->adjlist[c].firstarc=p;	
					}
					else//string2[1]=='w'
					{	
						num=c*10+1;
						tum=a*10;
						p=(ArcNode*)malloc(sizeof(ArcNode));
						p->sexnum=tum;
						p->nextarc=Wife->adjlist[c].firstarc;
						Wife->adjlist[c].firstarc=p;
						
					}
					p=(ArcNode*)malloc(sizeof(ArcNode));
					p->sexnum=num;
					p->nextarc=Husband->adjlist[a].firstarc;
					Husband->adjlist[a].firstarc=p;	
				}
				else
				{
					
					c=string2[0]-'0';
					if(string2[1]=='h')
					{
						num=c*10;
						tum=a*10+1;	
						p=(ArcNode*)malloc(sizeof(ArcNode));
						p->sexnum=tum;
						p->nextarc=Husband->adjlist[c].firstarc;
						Husband->adjlist[c].firstarc=p;	
					}
					else//string2[1]=='w
					{
						num=c*10+1;
						tum=a*10+1;	
						p=(ArcNode*)malloc(sizeof(ArcNode));
						p->sexnum=tum;
						p->nextarc=Wife->adjlist[c].firstarc;
						Wife->adjlist[c].firstarc=p;	
					}
					p=(ArcNode*)malloc(sizeof(ArcNode));
					p->sexnum=num;
					p->nextarc=Wife->adjlist[a].firstarc;
					Wife->adjlist[a].firstarc=p;	
				}
			}
			Back_Bride(1,n);
			scanf("%d%d",&n,&m);
			if(m==0 && n==0)first=0;
	}	
			return 0;
}