Zeray Rice

..

[USACO 3.3] Riding the Fences

解析

七桥问题而已… zhwp的解析是比较详细的.. 基本思路是找到最靠前的可以作为起点的点然后开始搜… 嗯

代码

USACO 3.3 Riding The Fences raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

/*
USER: fanzeyi1
TASK: fence
LANG: C++
*/
/*
 * =====================================================================================
 * 
 *       Filename:  fence.cc
 *        Version:  1.0
 *        Created:  2012年01月18日 18时44分09秒
 *       Compiler:  g++
 *         Author:  Zeray Rice <fanzeyi1994@gmail.com>
 * 
 * =====================================================================================
 */
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

int n;
int map[503][503];
int solu[10000];
int p = 0;

void dfs(int starter) {
    for(int i = 1; i <= 500; i++) {
        if(map[starter][i]) {
            map[starter][i] = map[starter][i] - 1;
            map[i][starter] = map[i][starter] - 1;
            dfs(i);
        }
    }
    solu[p++] = starter;
}

int main() {
    FILE *fin = fopen("fence.in", "r");
    FILE *fout = fopen("fence.out", "w");
    int a, b;
    int starter = 0;
    fscanf(fin, "%d", &n);
    for(int i = 0; i < n; i++) {
        fscanf(fin, "%d %d", &a, &b);
        map[a][b] = map[a][b] + 1;
        map[b][a] = map[b][a] + 1;
        map[a][0] = map[a][0] + 1;
        map[b][0] = map[b][0] + 1;
    }
    for(int i = 1; i <= 500; i++) {
        if(map[i][0] % 2 == 1) {
            starter = i;
            break;
        }
    }
    if(starter == 0) {
        for(int i = 1; i <= 500; i++) {
            if(map[i][0]) {
                starter = i;
                break;
            }
        }
    }
    dfs(starter);
    for(int i = p - 1; i >= 0; i--) {
        fprintf(fout, "%d\n", solu[i]);
    }
    return 0;
}

At last, 春节快乐～

Comments