| ||||||||||
| 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