Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

dfs无数次WA,求测试数据

Posted by kenby123 at 2010-12-10 11:51:58 on Problem 2492
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

int		n, m;
char	found;		/* 是否存在一种性别方案,使所有虫子都不是同性恋 */
char	sex[2005];	/* 记录每个虫子的性别 */
char	interaction[1000000][2];	/* 记录所有交配记录 */

static int compare(const void *p1, const void *p2)
{
	return *((char *)p1) - *((char *)p2);
}

void print_sex() 
{
	int		i;

	for (i = 1; i <= n; i++) {
		if (sex[i]) {
			printf("%d ", i);
		}
	}
	printf("\n");
	for (i = 1; i <= n; i++) {
		if (sex[i]) {
			printf("%c ", sex[i]);
		}
	}
	printf("\n");
}

/* 给第i次交配的两只虫子确定性别 */
void dfs(int i)
{
	int		j;
	char	*sex1, *sex2;

#ifdef DEBUG
	print_sex();
#endif
	sex1 = sex + interaction[i][0];
	sex2 = sex + interaction[i][1];
	if (i == m) {
		debug("没有同性恋,%d只虫子的性别为:\n", n);
		for (j = 1; j <= n; j++) {
			debug("%d:%c ", j, sex[j]);
		}
		debug("\n");
		found = 1;
		return;
	}
	if (found)  return;
	// 两只虫子的性别都确定过,看它们是否是同性
	if (*sex1 && *sex2){
		if (*sex1 == *sex2) {
			debug("第%d次, 同性恋\n", i);
			return;
		}
		else {
			debug("第%d次合法\n", i);
			dfs(i+1);
			if (found)  return;
		}
	}	
	else if (*sex1 && !*sex2){
		*sex2 = (*sex1 == 'F' ? 'M' : 'F');
		debug("第%d次, %c%c\n", i, *sex1, *sex2);
		dfs(i+1);
		if (found)  return;
		*sex2 = 0;
	}
	else if (!*sex1 && *sex2){
		*sex1 = (*sex2 == 'F' ? 'M' : 'F');
		debug("第%d次, %c%c\n", i, *sex1, *sex2);
		dfs(i+1);
		if (found)  return;
		*sex1 = 0;
	}
	else if (!*sex1 && !*sex2){
		*sex1 = 'F';
		*sex2 = 'M';
		debug("第%d次都不知道, 先令%c%c\n", i, *sex1, *sex2);
		dfs(i+1);
		if (found)  return;
#ifdef DEBUG
		*sex1 = 0;
		*sex2 = 0;
		print_sex();
#endif
		*sex1 = 'M';
		*sex2 = 'F';
		debug("第%d次都不知道, 再令%c%c\n", i, *sex1, *sex2);
		dfs(i+1);
		if (!found) {
			debug("第%d次无论男女都会导致同性恋\n", i);
		}
	}
}

int main()
{
	int		t, i, j;
	char	fuck_me;

	scanf("%d", &t);
	for (i = 0; i < t; i++) {
		memset(sex, 0, sizeof(sex));
		fuck_me = 0;
		scanf("%d %d", &n, &m);
		printf("Scenario #%d:\n",i+1);
		for (j = 0; j < m; j++) {
			scanf("%d %d", &interaction[j][0], &interaction[j][1]);
			if (interaction[j][0] == interaction[j][1]) {
				fuck_me = 1;
			}
		}
		if (fuck_me) {
			printf("Suspicious bugs found!\n\n");
			continue;
		}
		qsort(interaction, m, sizeof(char)*2, compare);
		found = 0;
		sex[interaction[0][0]] = 'M';
		sex[interaction[0][1]] = 'F';
		debug("第%d次, %c%c\n", 0, 'M', 'F');
		dfs(1);

		if (found || m == 0) {
			printf("No suspicious bugs found!\n\n");
		}
		else {
			printf("Suspicious bugs found!\n\n");
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator