路径保存的问题

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

Mr_Wolfram @ 2017-09-21 20:44:30

#include <iostream>
#include <cstdio>
using namespace std;
int g[502][502],path[20000],f,mi,ma,pa,in[505],out[505],start=1;
void dfs(int k){
    //path[++pa]=k;
    for(int i=mi;i<=ma;i++){
        if(g[k][i]){
            g[k][i]--;g[i][k]--;
            dfs(i);
        }
    }
    path[++pa]=k;
}
int main(){
    freopen("in.txt","r",stdin);
    scanf("%d",&f);
    for(int i=1;i<=f;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x][y]++;g[y][x]++;
        mi=min(mi,min(x,y));
        ma=max(ma,max(x,y));
        in[y]++;in[x]++;
    }
    for(int i=mi;i<=ma;i++){
        if(in[i]%2) {start=i;break;}
    }
    dfs(start);
    for(int i=pa;i>=1;i--) printf("%d\n",path[i]);
    fclose(stdin);
    return 0;
}
如果在递归开始时就记录路径会WA两个点

by Mr_Wolfram @ 2017-09-21 20:45:20

不明白在开始时记录路径和在结束时记录路径有什么区别


by lonely_icebear @ 2018-06-04 13:04:37

+1


|