玄学

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

Caro23333 @ 2017-08-01 08:33:11

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 1005;
int a[MAXN][MAXN],d[MAXN];
int maxp = 0,minp = 1<<30;
int n; 
int ans[MAXN];
void dfs(int x)
{
    printf("%d\n",x);
    for(int i = minp; i<=maxp; i++)
    {
        if(a[x][i])
        {
            a[x][i]--;
            a[i][x]--;
            dfs(i);
        }
    }
    //ans[++n] = x;
} 
int main()
{
    int f;
    cin >> f;
    int x,y;
    for(int i = 1; i<=f; i++)
    {
        scanf("%d%d",&x,&y);
        a[x][y]++;
        a[y][x]++;
        d[x] += 1;
        d[y] += 1;
        maxp = max(maxp,max(x,y));
        minp = min(minp,min(x,y)); 
    }
    int i;
    for(i = minp; i<=maxp; i++)
    {
        if(d[i]%2)
        {
            dfs(i);
            break;
        }
    }
    if(i==maxp+1)
        dfs(1);
 //   for(int j = n; j>=1; j--)
   //     printf("%d\n",ans[j]);
    system("pause");
    return 0;
}
我想问,dfs里面的部分为什么不能直接输出答案?改成将路径存到ans数组就AC了

by scarborough_fair @ 2017-08-01 10:30:54

dfs里的ans是在回退时存储的,编号当然是倒着打的


by Caro23333 @ 2017-08-01 11:16:17

@changyu2 但是直接输出也有74分啊


by WilliamPen @ 2017-10-01 20:54:17

因为如果搜到一个无法往下搜的点,一定是终点,会优先进队,如果其他还有什么环,会继续按顺序进队,你画个搜索树模拟一下试试


by WilliamPen @ 2017-10-01 20:54:51

然后楼下马上来正解


by cn_lemon @ 2017-10-01 20:54:57

@ Caro23333 给你一个数据:

6 1 2 2 3 3 4 3 5 3 6 5 6 然后你把这个图画出来,在写出它的搜索树,模拟数组存储顺序就知道了


by cn_lemon @ 2017-10-01 20:58:20

@Caro23333 当你搜索3号点的时候,你会去搜索4这个度为1的点,并且无法继续向下搜索了,所以你的搜索在4这里出现了第一个叶子节点,所以4这个本来应该是终点的点永远最先进队,满足条件,如果你在搜索过程中输出,就会在搜完3之后把4在中途输出,你就完蛋了


by xunzhen @ 2018-01-03 18:03:29

@cn_lemon 回答得非常好,我本来也不理解


by qwerta @ 2018-07-28 17:17:18

@cn_lemon 谢谢QAQ


|