| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
dfs无数次WA,求测试数据#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator